文档介绍：模式匹配的一种改进算法
,因此人们称它为克努特—莫里斯—普拉特操作(简称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
,在第三趟的匹配中,当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指针没有回溯,。
现在讨论一般情况。假设主串位‘s1s2…sn’,模式串为‘p1p2…pm’,从上例的分析可知,为实现改进算法,需要解决下述问题:当匹配过程中产生“失配”(即si≠pj)时,模式串“向右滑动”可行的距离有多远,换句话说,当主串中第i个字符与模式中第j个字符“失配”(即比较不等)时,主串中第i个字符(i指针不回溯)应与模式中哪个字符再比较?
假设此时应与模式中第k(k<j)个字符继续比较,则模式中前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个字符与主串中相应字符“失配”时,在模式中需重新和该字符进行比较的