模式匹配的一种改进算法----KMP 算法
这种改进算法是 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发现的，因此人们称它为
克努特-莫里斯-普拉特算法（简称为 KMP 算法）。该算法可以在 O(
n
+
m
)的时间数量级上完成
串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯 i 指
针，而是利用已经得到的‘部分匹配’的结果将模式向右‘滑动’尽可能远的一段距离后，
继续进行比较。
回顾例 4.1，见图 4.1 的匹配过程示例，在第三趟的匹配中，当
i
=6、
j
=4 字符比较不
等时，又从
i=3
、
j=0
重新开始比较。然后，经过仔细观察可发现，在
i
=3 和
j
=0，
i
=4 和
j
=0
以及
i
=5 和
j=0
这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串
中第 4、5、6 个字符必然是 b、c、a，（即模式串中第 2、3 和 4 个字符）。因为模式中的第
一个字符是 a，因此它无需再和这三个字符进行比较，而仅需将模式向右滑动三个字符的位
置继续进行
i
=6、
j
=1 时的字符比较即可。同理，在第一匹配中出现字符不等时，仅需将模
式向右移动两个字符的位置进行
i
=2、
j
=0 时的字符比较。因此，在整个匹配的过程中，i
指针没有回溯，如图 f-1 所示。
一般情况下，假设主串为
s
0
s
1
…s
n-1
，模式串为
p
0
p
1
…p
m-1
，从上例的分析可知，为了实
现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即
s
i
≠p
j
）时，模式串“向
右滑动”可行的距离有多远，换句话说，当主串中字符
S
i
与模式中字符
P
j
“失配”（即比
较不等）时，主串中字符
S
i
（
i
指针不回溯）应与模式中哪个字符再比较？
假设此时主串中字符 S
i
应与模式中字符
P
k
（k＜j）继续比较，则模式中字符
P
k
前面
k
个字符的子串必须满足下列关系式（f-1），且不存在
k'
＞
k
满足下列关系式（f-1）
p
0
p
1
…p
k-
1
=
s
i-k
s
i-k+
1
…s
i-
1
(f-1)
如图 f-2 所示。
当主串中字符 S
i
与模式中字符 P
j
“失配”时，已经得到的“部分”匹配结果是：
