KMP算法(改进版).doc

4.3.2 模式匹配的一种改进算法这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特莫里斯普拉特操作（简称KMP算法）。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。下面先从具体例子看起。 i=3第一趟匹配 a b a b c a b c a c b a b a b c j=3 i3第二趟匹配 a b a b c a b c a c b a b a b c a c j=5 j=1 i i=11第三趟匹配 a b a b c a b c a c b a b (a)b c a c 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所示。现在讨论一般情况。假设主串位s1s2sn，模式串为p1p2pm，从上例的分析可知，为实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即sipj）时，模式串“向右滑动”可行的距离有多远，换句话说，当主串中第i个字符与模式中第j个字符“失配”（即比较不等）时，主串中第i个字符（i指针不回溯）应与模式中哪个字符再比较？假设此时应与模式中第k（kk，满足下列关系式（4-2）p1p2pk-1=si-k+1s i-k+2si-1 (4-2)而已经得到的“部分匹配”的结果是pj-k+1p j-k+2p j-1=si-k+1s i-k+2si-1 (4-3)由(4-2)和(4-3)推得下列等式p1p2pk-1=pj-k+1p j-k+2p j-1 (4-4)反之，若模式串中存在满足式(4-4)的两个字串，则当匹配过程中，主串中第i个字符与模式中第j个字符比较不等时，仅需将模式向右滑动至模式中第k个字符和主串中第i个字符对齐，此时，模式中头k-1个字符的字串p1p2pk-1必定与主串中第i个字符之前长度为k-1的字串si-k+1s i-k+2si-1相等，由此，匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。若令nextj=k，则nextj表明当模式中第i个字符与主串中相应字符“失配”时，在模式中需重新和该字符进行比较的字符的位置。由此可引出模式串的next函数的定义： 0 当j=1时nextj= maxk|1kj且p1pk-1=pj-k+1p j-k+2p j-1 (4-5)1 其它情况由此定义可推出下列模式串的next函数值j12345678模式串abaabcacnextj01122312在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串好模式中正待比较的字符，令i的初值为pos，j的初值为1,。若在匹配过程中si=pj，则i和j分别增1，否则，i不变，而j退到nextj的位置再比较。若相等，则指针各自增1，否则，j再退到nextj的位置再比较，若相等，则指针各自增1，继续进行匹配；另一种是j退到某个next值(nextnextnextj)时字符比较相等，则指针各自增1，继续进行匹配；另一种是j退到0(即模式的第一个字符“失配”)，则此时须将模式继续向右滑行一个位置，即从主串的下一个字符s i+1起模式重新开始匹配。图4.5所示正是上述匹配过程的一个例子。 i=2第一趟 主串 a c a b a a b a a b c a c a a b c模式 a b j=2 next2=1 i=2第二趟 主串 a c a b a a b a a b c a c a a b c模式 a j=1 next1=0 i=3第三趟 主串 a c a b a a b a a b c a c a a b c模式 a b a a b c j=1j=6 next6=3 i=8 i=14第四趟 主串 a c a b a a b a a b c a c a a b c模式 (a b)a a b c a c j=3 j=9KMP算法如算法4.6所示，它在形式上和算法4.5极为相似。不同之处仅在于：当匹配过程中产生“失配”是，指针i不变，指针j退到nextj所指示的位置上重新进行比较，并且当指针j退至0时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1个字符起重新进行匹配。int index_KMP(SString S,SString T,int pos) /利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 / KMP算法。其中T非空，1posStrLength(S)。 i=pos; j=1;while ( i=S 0 & jT 0 ) return i-T 0 ; else return 0;算法4.6KMP算法是在已知模式串的next函数值的基础上执行的，那么，如何求得模式串的next函数值呢？从上述讨论可见，此函数值仅取决于模式串本身而和相匹配的主串无关。我们可从分析其定义出发用递推的方法求得next函数值。由定义得知 next1=0 (4-6)设nextj=k，这表明在模式串中存在下列关系： p1pk-1=pj-k+1p j-1 (4-7)其中k为满足1kk，满足等式(4-7)。此时nextj+1=？可能有两种情况：(1) 若pk=pj，则表明在模式串中 p1pk-1=pj-k+1pj-1 (4-8)并且不可能存在kk满足等式(4-8)，这就是说nextj+1=k+1，即 nextj+1= nextj+1 (4-9)(2) 若pkpj，则表明在模式串中p1pk-1 pj-k+1p j-1此时可把求next函数值的问题看成是一个模式匹配的问题，整个模式串即使主串有是模式串，而当前在匹配的过程中，已有pj-k+1=p1，pj-k+2=p2，pj-1=pk-1，则当pjpk时，应将模式向右滑动已知模式中的第nextk个字符和主串中的第j个字符相比较。若nextk=k，且pj=pk，则说明在主串中第j+1个字符之前存在一个长度为k(即next k)的最长字串，和模式串中从首字符起长度为k的字串相等，即 p1pk=pj-k+1pj-1 (1kkj) (4-10)这就是说 nextj+1= k+1即 nextj+1= nextk+1 (4-11)同理，若pjpk，则将模式继续向右滑动直至将模式中第nextk个字符和pj对齐，依次类推，直至pj和模式中某个字符匹配成功或者不存在任何k(1kj)满足等式(4-10)，则 nextj+1= 1 (4-12)例如：图4.6中的模式串，已求得前6个字符的next函数值，先求next7，因为next6=3，又p6p3，则需比较p6与p1(因为next3=1)，这相当于将字串模式向右滑动。由于p6p1，而且next1=0，所以next7=1，而因为p7=p1，则next8=2。根据上述分析所得结果(式(4-6)、(4-9)、(4-11)和(4-12)，仿照KMP算法，可求得next函数值的算法，如算法4.6所示。void get_next(SString T,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; else j=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函数在某些情况下尚有缺陷。例如模式a a a a b在和主串a b a a a a b 匹配时，当i=4,j=4时s.ch4 t.ch4,由nextj的指示还需要进行i=4、j=3,i=4、j=2,i=4、j=1等三次比较。实际上，因为模式中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式一气向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。这就是说，若按上述定义得出nextj=k,而模式中pj = pk ,则当主串中字符si和pj比较不等时，不需要再和pk进行比较，而直接和pnextk进行比较，换句话说，此时的nextj应和nextk相同。由此可得计算next函数修正值的算法如算法4.8所示。此时匹配算法不变。 void get_nextval(SSt