的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。如果使用KMP匹配算法，就不必回溯对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为Om
，因此在多数的实际应用场合下被应用。
5串的模式值
ext
的求取
51定义
（1）
ext01意义：任何串的第一个字符的模式值规定为1。（2）
extj1意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但TkTj）（1≤kj）。如：T”abCabCad”则
ext61，因T3T6（3）
extjk意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且TjTk（1≤kj）。即T0T1T2Tk1TjkTjk1Tjk2Tj1且TjTk（1≤kj）4
extj0意义：除（1）（2）（3）的其他情况。
52举例
1）求T“abcac”的模式函数的值。
ext01根据1
ext10根据4因3有1kjj1Tj1T0
ext20根据4因3有1kj（T0a）（T1b）
ext31根据2
ext41根据3T0T3且T1T4如下图：
5
f下标01234Tabcac
ext10011若T“abcab”将是这样：下标01234Tabcab
ext100102）求T”ababcaabc”的模式函数的值。
ext01根据1
ext10根据4
ext21根据2
ext30根据3虽然T0T2但T1T3被划入4
ext42根据3T0T1T2T3且T2T4
ext51根据2
ext61根据3T0T5且T1T6
ext70根据3虽然T0T6但T1T7被划入（4）
ext82根据3T0T1T6T7且T2T8如下图：下标012345678Tababcaabc
ext101021102
53意义
设在字符串S中查找模式串T，若SmT
那么，取T
的模式函数值
ext
。1
ext
1表示Sm和T0间接比较过了，不相等，下一次比较Sm1和T02
ext
0表示比较过程中产生了不相等，下一次比较Sm和T0。3
ext
k0但k
表示Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk。4其他值，不可能。
54代码
方法一：voidget_
extvalco
stcharTi
t
ext求模式串T的
ext函数值并存入数组
ext。i
tj0k1
ext01whileTj0ifk1TjTk
6
fjkifTjTk
extjkelse
extj
extkelsek
extk方法二：voidgetNextco
stcharpatter
i
t
ext
ext01i
tk1j0whilepatter
j0ifk1patter
kpatter
jk
extkjkifpatter
kpatter
j
extj
extkelse
extjk
6优化
KMP算法是可以r