模式匹配的 KMP 算法详解 这种由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 同时发现的改进的模式匹配算法简称为 KMP 算法。大概学过信 息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般 的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { } i=pos;j=1;//这里的串的第 1 个元素下标是 1 while(i<=S.Length && j<=T.Length) { } if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) if(j>T.Length) return i-T.Length;//匹配成功 else return 0; 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要 回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由 T 串本身的性质决定的，是因为 T 串本身有前后'部分匹配'的性质。如 果 T 为 abcdef 这样的，大没有回溯的必要。 改进的地方也就是这里，我们从 T 串本身出发，事先就找准了 T 自身前后部分匹配的位置，那就可以改进 算法。 如果不用回溯，那 T 串下一个位置从哪里开始呢？ 

还是上面那个例子，T 为 ababc，如果 c 失配，那就可以往前移到 aba 最后一个 a 的位置，像这样： ...ababd... ababc ->ababc 这样 i 不用回溯，j 跳到前 2 个位置，继续匹配的过程，这就是 KMP 算法所在。这个当 T[j]失配后，j 应 该往前跳的值就是 j 的 next 值，它是由 T 串本身固有决定的，与 S 串无关。 《数据结构》上给了 next 值的定义： 0 如果 j=1 next[j]={Max{k|1aaab ->aaab ->aaab 像这样的 T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可 能的向右滑移最短的长度。 OK，了解到这里，就看清了 KMP 的大部分内容，然后关键的问题是如何求 next 值？先不管它，先看如何用 它来进行匹配操作，也就是说先假设已经有了 next 值。 将最前面的程序改写成： int Index_KMP(String S,String T,int pos) { i=pos;j=1;//这里的串的第 1 个元素下标是 1 while(i<=S.Length && j<=T.Length) { if(j==0 || S[i]==T[j]){++i;++j;} //注意到这里的 j==0,和++j 的作用就知道为什么规定 next[1]=0 的好处了 else j=next[j];//i 不变（不回溯）,j 跳动 } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 

OK,是不是非常简单？还有更简单的，求 next 值，这也是整个算法成功的关键，从 next 值的定义来求太恐 怖了，怎么求？前面说过了，next 值表达的就是 T 串的自身部分匹配的性质，那么，我只要将 T 串和 T 串 自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从 T[1]和 T[2]开始匹配， 给出算法如下： void get_next(String T,int &next[]) { } i=1;j=0;next[1]=0; while(i<=T.Length) { } if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/} else j=next[j]; 看这个函数是不是非常像 KMP 匹配的函数，没错，它就是这么干的！注意到(2)语句逻辑覆盖的时候是 T[i]==T[j]以及 i 前面的、j 前面的都匹配的情况下，于是先自增，然后记下来 next[i]=j，这样每当 i 有 自增就会求得一个 next[i]，而 j 一定会小于等于 i，于是对于已经求出来的 next，可以继续求后面的 next， 而 next[1]=0 是已知，所以整个就这样递推的求出来了，方法非常巧妙。 这样的改进已经是很不错了，但算法还可以改进，注意到下面的匹配情况： ...aaac... aaaa. T 串中的'a'和 S 串中的'c'失配，而'a'的 next 值指的还是'a'，那同样的比较还是会失配，而这样的比较 是多余的，如果我事先知道，当 T[i]==T[j]，那 next[i]就设为 next[j]，在求 next 值的时候就已经比较 了，这样就可以去掉这样的多余的比较。于是稍加改进得到： void get_nextval(String T,int &next[]) { i=1;j=0;next[1]=0; while(i<=T.Length) { if(j==0 || T[i]==T[j]) { ++i;++j; if(T[i]!=T[j]) next[i]=j; else next[i]=next[j];//消去多余的可能的比较,next 再向前跳 } else j=next[j]; } } 匹配算法不变。