KMP算法(改进版).docVIP

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 ↓ i━━━━→3 第二趟匹配 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所示。 现在讨论一般情况。假设主串位‘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+1s i-k+2…si-1’ (4-2) 而已经得到的“部分匹配”的结果是 ‘pj-k+1p j-k+2…p j-1’=’si-k+1s i-k+2…si-1’ (4-3) 由(4-2)和(4-3)推得下列等式 ‘p1p2…pk-1’=‘pj-k+1p j-k+2…p j-1’ (4-4) 反之，若模式串中存在满足式(4-4)的两个字串，则当匹配过程中，主串中第i个字符与模式中第j个字符比较不等时，仅需将模式向右滑动至模式中第k个字符和主串中第i个字符对齐，此时，模式中头k-1个字符的字串’p1p2…pk-1’必定与主串中第i个字符之前长度为k-1的字串’si-k+1s i-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+1p j-k+2…p j-1’} (4-5) 其它情况 由此定义可推出下列模式串的next函数值 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next[j] 0 1 1 2 2 3 1 2 在求得模式的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]