KMP算法开始学的时候很不好理解,自己写了篇总结一下放在这里,使自己的思路清晰一下。
KMP算法之所以能够以o(m+n)(m为模式串长度,n为匹配串长度)的复杂度完成字符串匹配,是因为KMP算法不同于朴素的算法要进行匹配串指针的回溯。举个例子,对朴素的算法,如果要在”aadadefgadk“中匹配"adk“,首先比较"aad"与"adk",发现不匹配,然后再比较"ada"与"adk",考虑一种极端情况"aaaaaaaac"(有8个a)与"aaaaaaac"(有7个a),朴素地匹配时,当匹配串的指针指向第8个字符(a)、模式串的指针指向第8个字符(c)的时候,发现不相等了,于是匹配串的字符不得不回溯到第2个字符,模式串回溯到第1个字符,然后经过8次比较,才发现匹配。所以,如果经常出现比较"功败垂成"的情况,高频率的回溯必将增加复杂度,使其达到o(m*n)。
KMP算法之所以能够克服匹配串指针的回溯,只进行模式串指针的回溯,是因为它有一个next数组,这个数组可以在某一个字符匹配失败的时候,让模式串指针回溯到一个位置,模式串字符的这个位置以前所有的字符都和匹配串中的字符匹配。
举个例子:当"abcabdabeabf"与"abcabdabeabcabdabeabf"进行匹配的时候,发现不匹配了:
a b c a b d a b e a b c a b d a b e a b f
a b c a b d a b e a b f
此时,模式串的指针会指向c,匹配串的指针不变,也就是:
a b c a b d a b e a b c a b d a b e a b f
a b c a b d a b e a b f
再继续比较下去。
所以,关键在于求得next数组里的值,再看个例子:
a a a a a a a a a a a a a a a c
a a a a a a a a a a a a a a c
通过next数组,匹配串指针回溯,会变成:
a a a a a a a a a a a a a a a c
x a a a a a a a a a a a a a a c
此时给出next数组的含义:假设M为模式串,next[j]的值为k,如果k>0,那么M[0....k-1]和M[j-k.....j-1]是匹配的,并且0...k-1这个序列一定是最长的能够和j-k....j-1匹配的,另外为了后续的递推求next,会规定一些值,
即:
1)next[j]=-1 (j=0)
2)next[j]=max(k),k(0 3)next[j]=0 其他 举例来说,a a a c,next数组的值依次为 -1 0 1 2; a b c a b d a b e,next数组的值依次为 -1 0 0 0 1 2 0 1 2; 这样,每次在模式串与匹配串匹配失败的时候,会找到一个合理的位置,使得这个位置以前,模式串与匹配串仍然匹配,这是因为:假设S为匹配串,M为模式串,此时在S[n]处,M[j]处,匹配失败,但是此时会有M[0....j-1]与S[n-j....n-1]匹配成功,又由于M[0...k-1]与 M[j-k...j-1]相同,而且它们都是M[0....j-1]的字串,所以M[0....k-1]与S[n-j...n-1]是匹配成功的。 求next和KMP的代码如下: 根据题目的要求再进行增删即可。//M为模式串
void get_next(void)
{int i=0,j=-1,len=strlen(M);next[0]=-1;while(i<len){if(j==-1||M[i]==M[j]){i++;j++;next[i]=j;}else{j=next[j];}}
}
//M为模式串,S为匹配串
void kmp(void)
{int lenM=strlen(M),lenS=strlen(s),i,posM=0,posS=0;for(i=0;i<=lenM;i++){next[i]=0;}get_next();while(posS<lenS){if(posM==-1||M[posM]==s[posS]){posM++;posS++;}else{posM=next[posM];}}
}