1、KMP 字符串模式匹配详解KMP 字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为 O(m*n);KMP 匹配算法。可以证明它的时间复杂度为 O(m+n).。一 简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S , char T , int pos )/*若串 S 中从第 pos(S 的下标 0pos起存在和串 T 相同的子串，则称匹配成功，返回第一个这样的子串在串 S 中的下标，否则返回 -1 */int i = pos, j = 0;while ( Si+j != 0 /继续比较后一字符elsei +; j
2、= 0;/重新开始新的一轮匹配if ( Tj = 0)return i; /匹配成功 返回下标elsereturn -1;/串 S 中 (第 pos 个字符起 )不存在和串 T 相同的子串/ Index_BF此算法的思想是直截了当的：将主串 S 中某个位置 i 起始的子串和模式串 T 相比较。即从 j=0起比较 Si+j与 Tj，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后比较( j 逐步增1 )，直至与 T 串中最后一个字符相等为止，否则改从 S 串的下一个字符起重新开始进行下一轮的”匹配”，即将串 T 向后滑动一位，即 i 增1，而 j 退回至 0，重新开始新一
3、轮的匹配。例如：在串 S=”abcabcabdabba”中查找 T=” abcabd”（我们可以假设从下标 0开始）:先是比较S0和 T0是否相等，然后比较 S1和 T1是否相等我们发现一直比较到 S5和 T5才不等。如图：当这样一个失配发生时，T 下标必须回溯到开始，S 下标回溯的长度与 T 相同，然后 S 下标增1,然后再次比较。如图：这次立刻发生了失配，T 下标又回溯到开始，S 下标增1,然后再次比较。如图：这次立刻发生了失配，T 下标又回溯到开始，S 下标增1,然后再次比较。如图：又一次发生了失配，所以 T 下标又回溯到开始，S 下标增1,然后再次比较。这次 T 中的所有字符都和 S
4、中相应的字符匹配了。函数返回 T 在 S 中的起始下标3 。如图：二. KMP 匹配算法还是相同的例子，在 S=”abcabcabdabba”中查找 T=”abcabd”，如果使用 KMP 匹配算法，当第一次搜索到 S5和 T5不等后，S 下标不是回溯到1，T 下标也不是回溯到开始，而是根据 T 中T5=d的模式函数值（next5=2，为什么？后面讲） ，直接比较 S5和 T2是否相等，因为相等，S 和 T 的下标同时增加;因为又相等，S 和 T 的下标又同时增加。 。 。最终在 S 中找到了 T。如图：KMP 匹配算法和简单匹配算法效率比较，一个极端的例子是：在 S=“AAAAAAAAB“(
5、100个 A)中查找 T=”AAAAAAAAAB”,简单匹配算法每次都是比较到 T 的结尾，发现字符不同，然后 T 的下标回溯到开始，S 的下标也要回溯相同长度后增 1，继续比较。如果使用 KMP 匹配算法，就不必回溯.对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为 O (m+n)，因此在多数的实际应用场合下被应用。KMP 算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子。为什么 T5=d的模式函数值等于2（next5=2） ，其实这个2表示 T5=d的前面有2个字符和开始的两个字符相同，且 T5=d不等于开始的两个字符之后的第三个字符（ T2=c）.如图：
6、也就是说，如果开始的两个字符之后的第三个字符也为d ,那么，尽管 T5=d的前面有2个字符和开始的两个字符相同，T5= d的模式函数值也不为2，而是为0。前面我说：在 S=”abcabcabdabba”中查找 T=”abcabd”，如果使用 KMP 匹配算法，当第一次搜索到 S5和 T5不等后，S 下标不是回溯到1，T 下标也不是回溯到开始，而是根据 T 中 T5=d的模式函数值，直接比较 S5和 T2是否相等。 。 。为什么可以这样？刚才我又说：“（ next5=2） ，其实这个2表示 T5=d的前面有 2个字符和开始的两个字符相同”。请看图 ：因为，S4 =T4，S3 =T3，根据 nex
7、t5=2，有 T3=T0，T4 =T1，所以 S3=T0，S4 =T1（两对相当于间接比较过了） ，因此，接下来比较S5和 T2是否相等。 。 。有人可能会问：S3和 T0，S4和 T1是根据 next5=2间接比较相等，那 S1和 T0，S2和 T0之间又是怎么跳过，可以不比较呢？因为 S0=T0，S1=T1，S2=T2，而T0 != T1, T1 != T2,= S0 != S1,S1 != S2,所以 S1 != T0,S2 != T0. 还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况啊。假设 S 不变，在 S 中搜索 T=“abaabd”呢？答：这种情况，当比较到 S2
8、和 T2时，发现不等，就去看 next2的值，next2=-1 ，意思是 S2已经和 T0间接比较过了，不相等，接下来去比较 S3和 T0吧。假设 S 不变，在 S 中搜索 T=“abbabd”呢？答：这种情况当比较到 S2和 T2时，发现不等，就去看 next2的值， next2=0，意思是 S2已经和 T2比较过了，不相等，接下来去比较 S2和 T0吧。假设 S=”abaabcabdabba”在 S 中搜索 T=“abaabd”呢？答：这种情况当比较到 S5和 T5时，发现不等，就去看 next5的值， next5=2，意思是前面的比较过了，其中，S5 的前面有两个字符和 T 的开始两个相
9、等，接下来去比较 S5和 T2吧。总之，有了串的 next 值，一切搞定。那么，怎么求串的模式函数值 nextn呢？（本文中 next 值、模式函数值、模式值是一个意思。 ）三.怎么求串的模式值 nextn定义：（1）next0= -1 意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1 意义：模式串 T 中下标为 j 的字符，如果与首字符相同，且 j 的前面的 1k 个字符与开头的1k个字符不等（或者相等但 Tk=Tj） （1 k如：T=” abCabCad”则 next6=-1，因 T3=T6（3）nextj=k 意义：模式串 T 中下标为 j 的字符，如果 j 的前面
10、k 个字符与开头的 k 个字符相等，且 Tj != Tk（1k即 T0T1T2。 。 。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1且 Tj != Tk.（1 k(4) nextj=0 意义：除（1） （2） （3 ）的其他情况。举例：01）求 T=“abcac”的模式函数的值。next0= -1 根据（1）next1=0 根据 (4) 因（3）有10但 k4. 其他值，不可能。四.求串 T 的模式值 nextn的函数说了这么多，是不是觉得求串 T 的模式值 nextn很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明 KMP 算法，写出这个函数的先辈，令我
11、佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。下面是这个函数:void get_nextval(const char *T, int next)/求模式串 T 的 next 函数值并存入数组 next。int j = 0, k = -1;next0 = -1;while ( Tj/*+1*/ != 0 )if (k = -1 | Tj = Tk)+j; +k;if (Tj!=Tk)nextj = k;elsenextj = nextk;/ ifelsek = nextk;/ while/这里是我加的显示部分/ for(int i=0;i/ cout/cout/ get_nextval
12、另一种写法，也差不多。void getNext(const char* pattern,int next)next0= -1;int k=-1,j=0;while(patternj != 0)if(k!= -1 +j;+k;if(patternk= patternj)nextj=nextk;elsenextj=k;/这里是我加的显示部分/ for(int i=0;i/ cout/cout下面是 KMP 模式匹配程序，各位可以用他验证。记得加入上面的函数#include #include int KMP(const char *Text,const char* Pattern) /const 表
13、示函数内部不会改变这个参数的值。if( !Text|!Pattern| Pattern0=0 | Text0=0 )/return -1;/空指针或空串，返回 -1。int len=0;const char * c=Pattern;while(*c+!=0)/移动指针比移动下标快。+len;/字符串长度。int *next=new intlen+1;get_nextval(Pattern,next);/求 Pattern 的 next 函数值int index=0,i=0,j=0;while(Texti!=0 /继续比较后继字符+j;elseindex += j-nextj;if(nextj!
14、=-1)j=nextj;/模式串向右移动elsej=0;+i;/whiledelete next;if(Patternj=0)return index;/匹配成功elsereturn -1;int main()/abCabCadchar* text=”bababCabCadcaabcaababcbaaaabaaacababcaabc”;char*pattern=”adCadCad”;/getNext(pattern,n);/get_nextval(pattern,n);coutendl;return 0;五其他表示模式值的方法上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得
15、到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义 next0= -1,但后面绝不会出现-1 ，除了next0，其他模式值 nextj=k(0k 下面给出几种方法的例子：表一。下标 0 1 2 3 4 5 6 7 8T a b a b c a a b c(1) next -1 0 -1 0 2 -1 1 0 2(2) next -1 0 0 1 2 0 1 1 2(3) next 0 1 0 1 3 0 2 1 3第三种表示方法,在我看来，意义不是那么明了，不再讨论。表二。下标 0 1 2 3 4T a b c a c(1)next -1 0 0 -1 1(2)next -1 0
16、0 0 1表三。下标 0 1 2 3 4 5 6 7T a d C a d C a d(1)next -1 0 0 -1 0 0 -1 0(2)next -1 0 0 0 1 2 3 4对比串的模式值第一种表示方法和第二种表示方法，看表一：第一种表示方法 next2= -1,表示 T2=T0，且 T2-1 !=T0第二种表示方法 next2= 0,表示 T2-1 !=T0,但并不管 T0和 T2相不相等。第一种表示方法 next3= 0,表示虽然 T2=T0，但 T1 =T3第二种表示方法 next3= 1,表示 T2 =T0,他并不管 T1和 T3相不相等。第一种表示方法 next5= -1
17、,表示 T5=T0，且 T4 !=T0，T3T4 !=T0T1，T2T3T4 !=T0T1T2第二种表示方法 next5= 0,表示 T4 !=T0，T3T4 !=T0T1，T2T3T4 !=T0T1T2，但并不管 T0和 T5相不相等。换句话说：就算 T5=x,或 T5=y,T5=9,也有 next5= 0。从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，第二种表示方法更单纯，不容易搞错。当然，用第一种表示方法写出的模式匹配函数效率更高。比如说，在串S=“adCadCBdadCadCad 9876543”中匹配串 T=“adCadCad”,用第一种表示方法写出的模式匹配函数,当
18、比较到 S6 != T6时，取 next6= -1（表三）,它可以表示这样许多信息：S3S4S5=T3T4T5=T0T1T2，而 S6 != T6，T6=T3=T0，所以 S6 != T0,接下来比较 S7和 T0吧。如果用第二种表示方法写出的模式匹配函数,当比较到 S6 != T6时，取 next6= 3（表三）, 它只能表示：S3S4S5= T3T4T5=T0T1T2，但不能确定 T6与 T3相不相等，所以，接下来比较 S6和 T3;又不相等，取 next3= 0，它表示 S3S4S5= T0T1T2，但不会确定 T3与 T0相不相等，即 S6和T0相不相等，所以接下来比较 S6和 T0，
19、确定它们不相等，然后才会比较 S7和 T0。是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的第二种表示方法？原因是：最开始，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的第二种表示方法，如图：她说：“next 函数值的含义是：当出现 Si !=Tj时，下一次的比较应该在 Si和 Tnextj 之间进行。 ”虽简洁，但不明了，反复几遍也没明白为什么。而她给出的算法求出的模式值是我这里说的第一种表示方法 next 值，就是前面的 get_nextval()函数。匹配算法也是有瑕疵的。于是我在这里发帖说她错了：http:/
20、nextj=k(0k书归正传，下面给出我写的求第二种表示方法表示的模式值的函数,为了从 S 的任何位置开始匹配T， “当出现 Si !=Tj时，下一次的比较应该在 Si和 Tnextj 之间进行。 ” 定义 next0=0。void myget_nextval(const char *T, int next)/求模式串 T 的 next 函数值（第二种表示方法）并存入数组 next。int j = 1, k = 0;next0 = 0;while ( Tj != 0 )if(Tj = Tk)nextj = k;+j; +k;else if(Tj != T0)nextj = k;+j;k=0;e
21、lsenextj = k;+j;k=1;/whilefor(int i=0;icoutcout/ myget_nextval下面是模式值使用第二种表示方法的匹配函数（next0=0）int my_KMP(char *S, char *T, int pos)int i = pos, j = 0;/pos(S 的下标 0poswhile ( Si != 0 +j; /继续比较后继字符else / a b a b c a a b c/ 0 0 0 1 2 0 1 1 2 /-1 0 -1 0 2 -1 1 0 2i+;j = nextj; /*当出现 Si !=Tj时，下一次的比较应该在 Si和 Tnextj 之间进行。要求 next0=0。在这两个简单示范函数间使用全局数组 next传值。 */whileif ( Tj = 0 )return (i-j); /匹配成功else
