KMP算法

转的 :)

KMP算法对大多数初学者来言是一项比较巨大的考验，特别是自学KMP算法者。很多资料对数学功底不牢固的学者来说看起来比较模糊，下面，通过例子，以结构化的方式分析KMP算法（注：本内容为不严格定义，只注重简单理解和运用，要求严格定义见相关书籍）：

一：研究KMP算法要用到哪些字符串

主串：S[]：a b a b c a b c a c b a b；被比较的串，i为下标，下标以1开始

子串：P[]：a b a a b c a c；需要在主串中寻找的串，j 为下标，下标以1开始

模式串：next[]，值由P[]计算出，下标以1开始，具体见下面

KMP算法与一般比较算法的区别之一就是其要锻造出这个模式串，模式串是由子串经过计算而来的附加串， KMP算法的第一步就是要计算模式串。

 

二：KMP算法是什么原理

这部分很多资料上都有比较详细的说明，如果数学功底不好的学者，这部分内容最好去询问已经学会了学者，可大大减少摸索时间。如果真的不明白，可先看下面算法过程，然后再回头看原理，也不失为一种有效的方法。

 

三：算法过程

1.计算模式串

计算方法：

1.当j=1时，next[1]=0；

2.当J>2时，next[j]的值为j位置前紧邻的字符串与子串第一个字符开始最大的相同子串数+1。如：

子串第一个字符开始：       a  b  a  a  b  c  a  c

          P[]：   a  b  a  a  b  c  a  c

         next[]： 0  1  1  2  2

要计算c的模式数值，其前紧邻的字符串与子串第一个字符开始最大的相同子串为红色标记的a b两个，所以c处值为2+1=3

3.其他情况next[]值为1；

用相同的方法，计算结果如下：

 

2.KMP算法查找子串

比较方法：

1.当S[i]=P[j]，则：i++，j++；

2.当S[i]！=P[j]，如果此时j！=0，则j=next[j]，再继续比较；

如果j=0 则i++，j++，再继续比较

 

具体比较如下：

第一次：

 

匹配串在不等处右移动j= next[j]=2；再进行第二次比较。

第二次：

 

匹配串在不等处右移动j= next[j]=1；再进行第三次比较。

第三次：

 

继续后移， 按相同的方法比较即可…

 

一个简单的测试代码如下 ：

#include

#include

 

int next[6];                   //匹配串

char T[]="dababcab";    //主串

char S[]="ababc";          //子串

 

void KMP()                         //KMP函数

{

int i=0,j=1;

while(i<8 && j<=5)

{

if(j==0||S[i]==T[j])

{

i++;j++;

}

else

j=next[j];

}

if(j>5)

cout<<"是否匹配：ok\n";

else

cout<<"是否匹配：no\n";

}

 

void NEXT()                       //求子串函数

{

int i=1,j=0;

next[1]=0;

while(i<5)

{

if(j==0||T[i]==T[j])

{

++i;++j;next[i]=j;

}

else

j=next[j];

}

}

 

int  main()

{     int i;

NEXT();

cout<<"模式串为：";

for(i=1;i<=5;i++)

cout<

cout<

KMP();

return 0;

}