KMP字符串模式匹配算法解释

// cout<

//cout<

下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数#include #include 这个参数的值。{

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') else }

return index;// 匹配成功

return -1;

int main()//abCabCad {

char* text=\ char*pattern=\ //getNext(pattern,n);

//get_nextval(pattern,n); return 0; }

cout<

五．其他表示模式值的方法

上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义next[0]= -1,但后面绝不会出现-1，除了next[0]，其他模式值next[j]=k(0≤k

法，我是从论坛上看到的，没看到详细解释，我估计是为那些这样的编程语言准备的：数组的下标从1开始而不是0。 下面给出几种方法的例子： 表一。T 下标 0a 1 2 3 4c 5a 6a 7 8c b a b b (1) next-1 0 -1 0 2 -1 1 0 2 (2) next (3) next 表二。 T-1 0 0 1 0 0 1 1 2 3 0 0 1 2 1 2 3 1 第三种表示方法,在我看来，意义不是那么明了，不再讨论。 下标 0a 1 2 3 4 b c A c (1)next 表三。T-1 0 0 -1 1 (2)next -1 0 10 20 3a1 下标 0a 4 5 6 7 d C0 d C0 a d (1)next-1 0 -1 0 -1 0 (2)next -1 0 0 0 1 2 3 4 对比串的模式值第一种表示方法和第二种表示方法，看表一： 第一种表示方法next[2]= -1,表示T[2]=T[0]，且T[2-1] !=T[0] 相等。 第二种表示方法next[2]= 0,表示T[2-1] !=T[0],但并不管T[0] 和T[2]相不 第一种表示方法next[3]= 0,表示虽然T[2]=T[0]，但T[1] ==T[3] 等。 第二种表示方法next[3]= 1,表示T[2] =T[0],他并不管T[1] 和T[3]相不相 第一种表示方法next[5]= -1,表示T[5]=T[0]，且T[4] !=T[0]，T[3]T[4] !=T[0]T[1]，T[2]T[3]T[4] !=T[0]T[1]T[2] 第二种表示方法next[5]= 0,表示T[4] !=T[0]，T[3]T[4] !=T[0]T[1] ，T[2]T[3]T[4] !=T[0]T[1]T[2]，但并不管T[0] 和T[5]相不相等。换句话说：就算T[5]==’x’,或 T[5]==’y’,T[5]==’9’,也有next[5]= 0 。 从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，第二种表示方法更单纯，不容易搞错。当然，用第一种表示方法写出的模式匹配函数效率更高。比如说，在串S=“adCadCBdadCadCad 9876543”中匹配串T=“adCadCad”, 用第一种表示方法写出的模式匹配函数,当比较到S[6] != T[6] 时，取next[6]= -1（表三）,它可以表示这样许多信息： S[3]S[4]S[5]==T[3]T[4]T[5]==T[0]T[1]T[2]，而S[6] != T[6]，

T[6]==T[3]==T[0]，所以S[6] != T[0],接下来比较S[7]和T[0]吧。如果用第二种表示方法写出的模式匹配函数,当比较到S[6] != T[6] 时，取next[6]= 3（表三）,它只能表示：S[3]S[4]S[5]== T[3]T[4]T[5]==T[0]T[1]T[2]，但不能确定T[6]与T[3]相不相等，所以，接下来比较S[6]和T[3];又不相等，取next[3]= 0，它表示S[3]S[4]S[5]== T[0]T[1]T[2]，但不会确定T[3]与T[0]相不相等，即S[6]和T[0] 相不相等，所以接下来比较S[6]和T[0]，确定它们不相等，然后才会比较S[7]和T[0]。是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。

为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的第二种表示方法？原因是：最开始，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的第二种表示方法，如图：

她说：“next 函数值的含义是：当出现S[i] !=T[j]时，下一次的比较应该在S[i]和T[next[j]] 之间进行。”虽简洁，但不明了，反复几遍也没明白为什么。而她给出的算法求出的模式值是我这里说的第一种表示方法next值，就是前面的get_nextval()函数。匹配算法也是有瑕疵的。于是我在这里发帖说她错了：6

http://community.csdn.net/Expert/topic/4413/4413398.xml?temp=.202724

现在看来，她没有错，不过有张冠李戴之嫌。我不知道，是否有人第一次学到这里，不参考其他资料和明白人讲解的情况下，就能搞懂这个算法（我的意思是不仅是算法的大致思想，而是为什么定义和例子中next[j]=k(0≤k

书归正传，下面给出我写的求第二种表示方法表示的模式值的函数,为了从S的任何位置开始匹配T，“当出现S[i] !=T[j]时，下一次的比较应该在S[i]和T[next[j]] 之间进行。” 定义next[0]=0 。