字符串匹配,KMP算法

1,算法简介
KMP算法是模式匹配算法的一种改进算法，是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯- 普拉特操作（简称KMP算法）。
2,算法核心
对字串进行预处理.
依靠get_next函数计算出子串中每个字符对应的next[j]的值，从而减少子串回溯的距离，减少时间复杂度。
3,算法性能
简单匹配算法的时间复杂度为O(m*n);可以证明KMP匹配算法的时间复杂度为O(m+n).
4,计算子串的模式函数值.
子串的模式函数值.next[i]有很多版本,这里介绍其中的一种.
定义：
(1)next[0]= -1 意义：任何串的第一个字符的模式值规定为-1
(2)next[j]= -1  意义：模式串T中下标为j的字符，如果与首字符相同,且j的前面的1-k个字符与开头的1-k个字符不等(或者相等但T[k]==T[j])(1≤k).
(3)next[j]=k    意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] (1≤k).
(4)其他情况0.

例如：T="abCabCad",对应的函数模式值为
-1: 第一个字符规定为1
0: T[1]前面的字符与开头没有字符相等
0: T[2]前面的字符与开头没有字符相等
-1: T[3]与首字符相同,且j的前面的1-k个字符与开头的1-k个字符不等
0: T[4]的前面1个字符与开头的1个字符相等，但T[4] == T[1]
0: T[5]的前面2个字符与开头的2个字符相等，但T[5] == T[2]
-1: T[6]与首字符相同,T[6]的前面3个字符与开头的3个字符相等,但T[6] == T[3]
4: T[7]的前面4个字符与开头的4个字符相等，且T[7] != T[4]


4,next 函数值究竟是什么含义，前面说过一些，这里总结。
设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
(1).next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0]
(2).next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。
(3).next[n]= k >0 但k<n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？
(4).其他值，不可能。

5,具体算法如下：

#include<iostream>
#include<string>
using namespace std;

//求模式串T的next函数值并存入数组next[]中。
void getNext(const char* pattern,int next[])
{
   next[0]=   -1;
   int k=-1,j=0;
   while(pattern[j] != '\0')
   {
      if(k!= -1 && pattern[k]!= pattern[j] )
             k=next[k];
      ++j;++k;
      if(pattern[k]== pattern[j])
             next[j]=next[k];
      else
             next[j]=k;
   }
    for(int i=0;i<j;i++)
        cout<<next[i]<<" ";
    cout<<endl;
}

int KMP(const char *Text,const char* Pattern)
{
       if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
              return -1;//空指针或空串，返回-1。
       int len=0;
       const char * c=Pattern;
       while(*c++!='\0') ++len;//字符串长度。
       int *next=new int[len];
       getNext(Pattern,next);//求Pattern的next函数值

       int index=0,i=0,j=0;
       while(Text[i]!='\0' && Pattern[j]!='\0' )
       {
              if(Text[i]== Pattern[j]) ++i,++j; // 继续比较后继字符
              else
              {
                     index += j-next[j]; //主串前进的步伐数 ,连续两次不等,index变为0
                     if(next[j]!=-1) j=next[j]; // 表示子串的前j个与当前的主串匹配.
                     else  j=0,++i; // 表示子串当前的主串根本不匹配,子串从头开始,主串移动到下一个字符.
              }
       }

       delete[] next;
       if(Pattern[j]=='\0')
              return index;// 匹配成功
       else
              return -1;
}


int main()
{
    char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";
    char*pattern="abCabCad";
    cout<<KMP(text,pattern)<<endl;
	return 0;
}