文档介绍：KMP字符串模式匹配详解
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
简单匹配算法
先来看一个简单匹配算= =，d，不等于开始的两个字符之后的第三个字符(T[2] =，c‘).如图：
T a b c a b d
0 1 2 3 4 5
也就是说，如果开始的两个字符之后的第三个字符也为'd，,那么，尽管T[5] = =，cT的前面有2个字符和开始的两个字符相同，T[5] = =，d，的模式函数值也不为2,而是为0。
前面我说：在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5]和T[5]不等后，S下标不是回溯到1, T下标也不是回溯到开始，而是根据T中T[5] = =，d，的模式函数值，直接比较S[5]和T[2]是否相等为什么可以这样？
刚才我又说："(next[5]=2),其实这个2表示T[5] = =，d，的前面有2个字符和开始的两个字符相同”。请看图:因为，S[4] ==T[4], S[3] ==T[3],根据 next[5] = 2,有T[3]==T[0], T[4] ==T[1], 所以S[3] = =T[0], S[4] ==T[1](两对相当于间接比较过了)，因此，接下来比较S[5]和T[2] 是否相等。
T |a|b|c|a|b|d
0 12 3 4 5
有人可能会问：S[3]和T[0], S[4]和T[l]是根据next[5]=2间接比较相等，那S[l]和T[0], S[2] 和T[0]之间又是怎么跳过，可以不比较呢？因为S[0]=T[0], S[1]=T[1], S[2]=T[2],而T[0] != T[l], T[l] != T[2], = = > S[0] != S[1],S[1] != S[2],所以 S[l] != T[0],S[2] != T[0],还是从理论上间接比较了。
有人疑问又来了，你分析的是不是特殊轻况啊。
假设S不变，在S中搜索T="abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-l,意思是S[2]已经和T[0]间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
假设S不变，在S中搜索T="abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0,意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]
和T[0]吧。
假设S=”abaabcabdabba”在S中搜索T="abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5] = 2,意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？(本文中next值、模式函数值、模式值是一个意思。)
怎么求串的模式值next[n]
定义：
next[O]= -1意义：任何串的第一个字符的模式值规定为-1。
next[j]=-1意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等(或者相等但T[k] = =T[j]) (l<k
如：T="abCabCad”ffl next[6] = -l,因 T[3]=T[6]
next[j] = k意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] (l<k
即 T[0]T[l]T[2]o„o T[k-l] = =T[j-k]T[j-k+l]T[j-k+2]...T[j-l]
且 T[j] != T[k]. (l<k
next[j]=O意义:除(1)(2)(3)的其他情况。
举例：
01)求T="abcac”的模式函数的值。
next[0]= -1 根据(1)
next[l]=0 根据(4)因(3)有l< = k
next[2]=0 根据(4)因(3)有l< = k
next[3]= -1 根据(2)
next[4] = l 根据(3) T[0]=T[3]且T[1]=T[4]
即
下标0 1 2 3 4
T a b c a c
next -10 0-11
若T="abcab”将是这样：
下标0 1 2 3 4
T a b c a b
next -10 0-10
为什么 T[0] = =T[3