这两天抱佛脚抱到数据结构的串的模式匹配部分，居然让这个破KMP算法给卡得死死的，左看右看看不明白。印象以前学数据结构时可是有把它给弄透了啊！于是google、baidu狂搜一通，看了N个网页后还是没有弄明白。唉，脑子不好使了。最后好不容易下了个电子版的《严蔚敏：数据结构（C语言版）》，啃了半天总算弄明白了。这次吸取教训，把理解到的写下来。
其实KMP算法还是比较容易理解的，关键在于next(j)函数容易让人糊涂，只要把这个函数弄明白了，KMP算也就可以说是真正掌握了。
要说清楚KMP算法，可以从朴素的模式匹配算法说起。朴素的模式匹配算法比较容易理解，其实现如下：（不得不题的是，2004年7月版的《软件设计师教程》中该算法的实现有误，460页倒数第三行的“i=1;”应该是“j=0;”才对。害我无端郁闷了好久）
int Index(char s[], char p[], int pos){ int i, j, slen, plen; i = pos; j = 0; slen = strlen(s); plen = strlen(p); while((i < slen) && (j < plen)) { if((s[i] == p[j])) { i++; j++; } else { i = i-j+1; j = 0; //如上所提，2004年7月版的《软件设计师教程》中该地方误为“i=1;”是不对的。该书中还有其它不少的错误之处，大家网上搜搜就知道。 } } if(j >= plen) { return (i-plen); } else { return -1; } }
可见，在朴素的模式匹配算法中，当模式中的p[j]与主串中的s[i]不匹配时，需要把主串的指针回溯到i-j+1的地方从新用s[i-j+1]跟p[0]进行匹配比较。KMP算法的想法是，能不能不回溯主串的指针呢？这种想法基于如下事实的：p[j]!=s[i]前，p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的（这里j>0，也就是说在不匹配前已经有匹配的字符了。否则如果j=0,则主串指针肯定不用回溯，直接向前变成i+1再跟p[0]比较就是了）
p[j]!=s[i]前，p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的，这说明了什么呢？这说明可以通过分析模式的p[0]~p[j-1]来分析s[i-j]~s[i-1]。如果模式中存在p[0]~p[k-1]=p[j-k]~p[j-1](共k个匹配的字符,且k是满足这个关系的最大值）,则可以知道s[i-k]~s[j-1]跟[0]~p[k-1]是匹配的，那么，s[i]只需要跟p[k]进行比较就行了。而这个k是跟主串无关的，只需要分析模式串就可以求出来（这就是普通的教材中next[j]=k这个假设的由来,普通教材中总喜欢假设这个k值已经有了，如果你逻辑思维强还没有什么，不然或多或少会把你卡在这的）。亦即next[j]=k。
如果上述的p[0]~p[k-1]=p[j-k]~p[j-1]串不存在会怎么样呢？这说明p[j]前的串中不存在p[0]...=...p[j-1]的情况，就连p[0]也不等于p[j-1],也就是说p[0]~p[j-1]中所有以p[j-1]为结尾的子串跟模式p都是失配的。基于上面p[0]~p[j-1]=s[i-j]~s[i-1]的事实，可以断定s[i-j]~s[i-1]中所有以s[i-1]结尾的子串跟模式p都是失配，这说明把主串的指针回溯到i-j+1～i-1都是没有必要的，既然没有必要回溯，而s[i]!=p[j]，则s[i只能跟p[0]进行比较匹配了。亦即next[j]=0。
特殊情况下，j=0，即s[i]!=p[0]，这时不用再用s[i]来跟p中的其它字符比较了，变成用s[i+1]跟p[0]进行比较。为了统一，可以让next[0]=-1。在下一轮的比较中，判断到j=-1的情况时，让i=i+1,j=j+1,自然就形成s[i+1]跟p[0]比较的效果了。
现在回过头来看教材上的next[j]的定义
|－ -1, 当 j = 0时 next[j] = |－ max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]' } |－ 0, 其它情况 是不是很容易理解呢？
时候再来看KMP的算法实现
int Index(char s[], char p[], int pos, int next[]){ int i, j, slen, plen; i = pos; j = 0; slen = strlen(s); plen = strlen(p); while((i < slen) && (j < plen)) { if((j == -1) || (s[i] == p[j])) { i++; j++; } else { j = next[j]; } } if(j >= plen) { return (i-plen); } else { return -1; } }
应该不会有什么疑问了吧？
现在剩下的就是GetNext怎么实现了。
根据上面的推导，知道next[0]=-1。如果已经知道next[j]=k，那么说明p[0]~p[k-1]=p[j-k]~p[j-1]，现在next[j+1]应该是多少呢？
若p[k]=p[j]，说明p[0]~p[k]=p[j-k]~p[j]成立，则有next[j+1]=k+1。
若p[k]!=p[j],即p[0]~p[k-1]!=p[j-k]~p[j-1]，从KMP算法的角度来看，这时应p[j]应该跟p[next[k]]进行比较。也就是k=next[k]，如此重复，由于next[k]<k，故最终必然是k=-1或p[k]=p[j]。如果是k=-1,则next[j+1]=0,否则next[j+1]=k+1，可以统一为next[j+1]=k+1。
下面就是GetNext函数的实现：
void GetNext(char p[],int next[]) { int i, j, slen; slen = strlen(p); i = 0; j = -1; next[0] = -1; while(i < slen) { if((j == -1) || (p[i] == p[j])) { i++; j++; next[i] = j; } else { j = next[j]; } } }
附加：
＃i nclude<stdio.h>#define max 100typedef struct{char data[max+1];int length;}String;int match_Bruce(String &S,String &T ){int i=1,j=1;while(i<=S.length&&j<=T.length){ if(S.data==T.data){i++;j++;}else {i=i-j+2;j=1;} } if(j>T.length)return i-T.length;else return 0;
}int match_kmp(String &S,String &T,int next[]){int i=1,j=1;while(i<=S.length&&j<=T.length){if(j==0||S.data==T.data[j]){i++;j++;}elsej=next[j];}if(j>T.length)return i-T.length;else return 0;}void get_next(String &T,int next[]){int i=1,j=0;next[1]=0;while(i<T.length){if(j==0||T.data==T.data[j]){i++;j++;next=j;}elsej=next[j];} }void get_nextval(String &T,int nextval[]){int i=1,j=0;nextval[1]=0;while(i<T.length){if(j==0||T.data==T.data[j]){i++;j++;if(T.data!=T.data[j])nextval=j;else nextval=nextval[j];}else j=nextval[j];}}
【一个免费送书的好网站，推荐给书虫们】
