KMP算法改进版

4.3.2模式匹配的一种改进算法这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。下面先从具体例子看起。↓i=3第一趟匹配ababcabcacbababc↑j=3↓i━━━━→3第二趟匹配ababcabcacbababcac↑━━→↑j=5j=1↓i━→i=11第三趟匹配ababcabcacbab(a)bcac↑━→j=6回顾4.3的匹配过程示例，在第三趟的匹配中，当i=7、j=5字符比较不等时，又从i=4、j=1重新开始比较。然后，经仔细观察可发现，在i=4和j=1，i=5和j=1以及i=6和j=1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可以得出，主串中第4、5和6个字符必然是‘b’、‘c’和‘a’（即模式串中第2、3和4个字符）。因为模式中的第一个字符是a，因此它无需再和这三个字符进行比较，而仅需将模式向右滑动三个字符的位置继续进行比较i=7、j=2的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式向右滑动两个字符的位置继续进行i=3、j=1时的字符比较。由此，在整个匹配的过程中，i指针没有回溯，如图4.4所示。现在讨论一般情况。假设主串位‘s1s2…sn’，模式串为‘p1p2…pm’，从上例的分析可知，为实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即si≠pj）时，模式串“向右滑动”可行的距离有多远，换句话说，当主串中第i个字符与模式中第j个字符“失配”（即比较不等）时，主串中第i个字符（i指针不回溯）应与模式中哪个字符再比较？假设此时应与模式中第k（kj）个字符继续比较，则模式中前k-1个字符的字串必须满足下列关系式（4-2），且不可能存在k’k，满足下列关系式（4-2）‘p1p2…pk-1’=‘si-k+1si-k+2…si-1’(4-2)而已经得到的“部分匹配”的结果是‘pj-k+1pj-k+2…pj-1’=’si-k+1si-k+2…si-1’(4-3)由(4-2)和(4-3)推得下列等式‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’(4-4)反之，若模式串中存在满足式(4-4)的两个字串，则当匹配过程中，主串中第i个字符与模式中第j个字符比较不等时，仅需将模式向右滑动至模式中第k个字符和主串中第i个字符对齐，此时，模式中头k-1个字符的字串’p1p2…pk-1’必定与主串中第i个字符之前长度为k-1的字串’si-k+1si-k+2…si-1’相等，由此，匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。若令next[j]=k，则next[j]表明当模式中第i个字符与主串中相应字符“失配”时，在模式中需重新和该字符进行比较的字符的位置。由此可引出模式串的next函数的定义：0当j=1时next[j]=max{k|1kj且’p1…pk-1’=’pj-k+1pj-k+2…pj-1’}(4-5)1其它情况由此定义可推出下列模式串的next函数值j12345678模式串abaabcacnext[j]01122312在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串好模式中正待比较的字符，令i的初值为pos，j的初值为1,。若在匹配过程中si=pj，则i和j分别增1，否则，i不变，而j退到next[j]的位置再比较。若相等，则指针各自增1，否则，j再退到next[j]的位置再比较，若相等，则指针各自增1，继续进行匹配；另一种是j退到某个next值(next[next[…next[j]…]])时字符比较相等，则指针各自增1，继续进行匹配；另一种是j退到0(即模式的第一个字符“失配”)，则此时须将模式继续向右滑行一个位置，即从主串的下一个字符si+1起模式重新开始匹配。图4.5所示正是上述匹配过程的一个例子。↓i=2第一趟主串acabaabaabcacaabc模式ab↑j=2next[2]=1↓i=2第二趟主串acabaabaabcacaabc模式a↑j=1next[1]=0↓i=3第三趟主串acabaabaabcacaabc模式abaabc↑j=1━━→j=6next[6]=3↓i=8━━━→↓i=14第四趟主串acabaabaabcacaabc模式(ab)aabcac↑j=3━━→↑j=9KMP算法如算法4.6所示，它在形式上和算法4.5极为相似。不同之处仅在于：当匹配过程中产生“失配”是，指针i不变，指针j退到next[j]所指示的位置上重新进行比较，并且当指针j退至0时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1个字符起重新进行匹配。intindex_KMP(SStringS,SStringT,intpos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的//KMP算法。其中T非空，1≦pos≦StrLength(S)。i=pos;j=1;while(i=S[0]&&j=T[0]){if(j==0||S[i]==T[j]){i++;j++;}elsej=next[j];}if(jT[0])returni-T[0];elsereturn0;}算法4.6KMP算法是在已知模式串的next函数值的基础上执行的，那么，如何求得模式串的next函数值呢？从上述讨论可见，此函数值仅取决于模式串本身而和相匹配的主串无关。我们可从分析其定义出发用递推的方法求得next函数值。由定义得知next[1]=0(4-6)设next[j]=k，这表明在模式串中存在下列关系：’p1…pk-1’=’pj-k+1…pj-1’(4-7)其中k为满足1kj的某个值，并且不可能存在k’k，满足等式(4-7)。此时next[j+1]=？可能有两种情况：(1)若pk=pj，则表明在模式串中’p1…pk-1’=’pj-k+1…pj-1’(4-8)并且不可能存在k’k满足等式(4-8)，这就是说next[j+1]=k+1，即next[j+1]=next[j]+1(4-9)(2)若pk≠pj，则表明在模式串中’p1…pk-1’≠’pj-k+1…pj-1’此时可把求next函数值的问题看成是一个模式匹配的问题，整个模式串即使主串有是模式串，而当前在匹配的过程中，已有pj-k+1=p1，pj-k+2=p2，…，pj-1=pk-1，则当pj≠pk时，应将模式向右滑动已知模式中的第next[k]个字符和主串中的第j个字符相比较。若next[k]=k’，且pj=pk，则说明在主串中第j+1个字符之前存在一个长度为k’(即next[k])的最长字串，和模式串中从首字符起长度为k’的字串相等，即’p1…pk’’=’pj-k’+1…pj-1’(1k’kj)(4-10)这就是说next[j+1]=k’+1即next[j+1]=next[k]+1(4-11)同理，若pj≠pk’，则将模式继续向右滑动直至将模式中第next[k’]个字符和pj对齐，……，依次类推，直至pj和模式中某个字符匹配成功或者不存在任何k’(1k’j)满足等式(4-10)，则next[j+1]=1(4-12)例如：图4.6中的模式串，已求得前6个字符的next函数值，先求next[7]，因为next[6]=3，又p6≠p3，则需比较p6与p1(因为next[3]=1)，这相当于将字串模式向右滑动。由于p6≠p1，而且next[1]=0，所以next[7]=1，而因为p7=p1，则next[8]=2。根据上述分析所得结果(式(4-6)、(4-9)、(4-11)和(4-12))，仿照KMP算法，可求得next函数值的算法，如算法4.6所示。voidget_next(SStringT,int&next[]){//求模式串T的next函数值并存入数组next。i=1;next[1]=0;j=0;while(iT[0]){if(j==0||T[i]==T[j]){i++;j++;next[i]=k;}elsej=next[j];}}//get_next算法4.7算法4.7的时间复杂度为o(m)。通常，模式串的长度m比主串的长度n要小得多，因此，对整个匹配算法来说，所增加的这点时间是值得的。最后，要说明两点：1）虽然算法4.5的时间复杂度是o(n*m),但在一般情况下，其实际的执行时间近似于o(n+m),但因此至今仍被采用。Kmp算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比算法4.5快很多。但是kmp算法的最大特点是指示主串的指针不需回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。2）前面定义的next函数在某些情况下尚有缺陷。例如模式‘aaaab’在和主串’abaaaab’匹配时，当i=4,j=4时s.ch[4]≠t.ch[4],由next[j]的指示还需要进行i=4、j=3,i=4、j=2,i=4、j=1等三次比较。实际上，因为模式中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式一气向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。这就是说，若按上述定义得出next[j]=k,而模式中pj=pk,则当主串中字符si和pj比较不等时，不需要再和pk进行比较，而直接和pnext[k]进行比较，换句话说，此时的next[j]应和next[k]相同。由此可得计算next函数修正值的算法如算法4.8所示。此时匹配算法不变。voidget_nextval(SStringT,int&nextval[]){//求模式串T的next函数修正值并存入数组nextval。i=1;nextval[1]=0;j=0;while(iT[0]){if(j==0||T[i]==T[j]){i++;j++;next[i]=k;if(T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];}elsej=nextval[j];}}//get_nextval