如果在完全匹配结束前发生不匹配，那么模式串T回溯到模式首字符，而主串S则回溯到起始位置的下一个字符进行比较。依次类推，直至模式串T和主串S中的一个子串相等，此时称为匹配成功，否则，称为匹配失败。图21展示了pos1时，模式串T’abcac’和主串S’ababcabcacbab’的匹配过程。其中i和j指示主串S和模式串T中当前正待比较的字符位置。串的简单模式匹配算法描述如算法21所示。
【算法描述】
i
ti
tijI
dexSStri
gSSStri
gTi
tpos
iposj1WhileiS0jT0ifSiTjijelseiij2j1
2
fifjT0elseretur
iT0
retur
0
算法21串的简单模式匹配
第1趟匹配ST
aa
↓i3babcbcac↑j3↓i2baab↑j1
abca
cb
ab
第2趟匹配ST
a
bcacac
bcacb
ab
第3趟匹配ST
a
baa
↓i7bcabcabcac↑j5
cb
ab
第4趟匹配ST
a
↓i4babcabcabcaca↑j1↓i5bcabcaabcac↑j1
cb
ab
第5趟匹配ST
a
ba
cb
ab
第6趟匹配ST
a
ba
bcaa
↓i11bcacbabbcac↑j6
图21串的简单模式匹配过程示意
这种算法看起来比较简单，但是效率比较低，最好的情况下为Om
，在最坏情况下，每趟比较都在最后出现不等，最多要比较
m1趟，总比较次数为O
m1m，算法的时间复杂度为Om
。22KMP算法
3
f221简述KMP（无回溯的模式匹配）算法正是由DEK
uth、VRPratt和JHMorris同时发现的，因此称KMP算法。它是针对上述算法频繁回溯的不足做了实质性的改进。其基本思想是：某趟匹配中，主串字符si和模式串tj匹配失败后，指针i不回溯，而是让模式串T向右“滑动”至某个位置，假设这个位置是k，使得tj对准si继续向右进行比较。因此，KMP算法的关键就在于找到模式串向右“滑动的距离”。若用数组元素
extj来表示字符tj不匹配时的滑动距离，则
extj的取值满足以下
ext函数的定义：
0
extjmaxk1kj且’t1t2…tk1’’tjk1tjk2…tj1’此集合不空时，取相等串中最长字串1其他情况
222KMP算法实现KMP算法是在求得模式串的
ext函数值的基础上执行的，
ext函数值仅依赖于模式T本身，而和主串S无关。由221中
ext函数的定义实现可得到模式串’abcaabbabcab’的
ext函数值，如表21所示。
表21模式串’abcaabbabcab’的
ext函数值
j
模式
extj
1a0
2b1
3c1
4a1
5a2
6b2
7b3
8a1
9b2
10c3
11a4
12b5
KMP算法如算法22所示，在形式上和算法21极为类似。假设模式串T1…m中前q个字符已经匹配了主串Ss…sq1，那我们就可以r