KMP之我见

传统的简单匹配算法O(m*n)：

 

int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符
起存在和串 T 相同的子串，则称匹配成功，返回第一个
这样的子串在串 S 中的下标，否则返回 -1    */
int i = pos, j = 0;
while ( S[i+j] != '/0'&& T[j] != '/0')
if ( S[i+j] == T[j] )
j ++; // 继续比较后一字符
else
{
i ++; j = 0; // 重新开始新的一轮匹配
}
if ( T[j] == '/0')
return i; // 匹配成功   返回下标
else
return -1; // 串S中(第pos个字符起)不存在和串T相同的子串
} // Index_BF

 KMP算法O(m+n)

1、首先求出模式串的模式值next[i]（当匹配失效出现时，失效字符前面的next[i]个字符与模式串的开头next[i]个字符串一样，下次比较的时候直接跳过前next[i]个字符）

模式值函数的定义：

（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。

（2）next[j]= -1   意义：模式串T中下标为j的字符，如果与首字符

相同，且j的前面的j—k个字符与开头的j—k

个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。

如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]

（3）next[j]=k    意义：模式串T中下标为j的字符，如果j的前面k个

字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。

                       即T[0]T[1]T[2]。。。T[k-1]==

T[j-k]T[j-k+1]T[j-k+2]…T[j-1]

且T[j] != T[k].（1≤k<j）;

(4) next[j]=0   意义：除（1）（2）（3）的其他情况

  

源程序如下：
void get_nextval(const char *T, int next[])
{
       // 求模式串T的next函数值并存入数组 next。
       int j = 0, k = -1;
       next[0] = -1;
       while ( T[j/*+1*/] != '/0' )
       {
              if (k == -1 || T[j] == T[k])
              {
                     ++j; ++k;
                     if (T[j]!=T[k])
                            next[j] = k;
                     else
                            next[j] = next[k];
              }// if
              else
                     k = next[k];
       }// while
    ////这里是我加的显示部分
   // for(int i=0;i<j;i++)
       //{
       //     cout<<next[i];
       //}
       //cout<<endl;
}// get_nextval　
另一种写法，也差不多。
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;
}

2、KMP匹配
#include <iostream.h>
#include <string.h>
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
       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+1];
       get_nextval(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];
                     if(next[j]!=-1)
                            j=next[j];// 模式串向右移动
                     else
                     {
                            j=0;
                            ++i;
                     }
              }
       }//while
   
       delete []next;
       if(Pattern[j]=='/0')
              return index;// 匹配成功
       else
              return -1;      
}
int main()//abCabCad
{
    char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";
    char*pattern="adCadCad";
       //getNext(pattern,n);
    //get_nextval(pattern,n);
      cout<<KMP(text,pattern)<<endl;
       return 0;
}

 

详细分析参考： http://blog.chinaunix.net/uid-27164517-id-3280128.html