KMP是一种在一个字符串中定义另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法的时间复杂度为O(m+n)。
一个极端的例子是:在S="AAAAAA...AAB"(100个A)中查找T="AAAAAAAAAB",简单匹配算法每次都是匹配到T的结尾,发现字符不同,然后T的下标回溯到开始,S的下标也要回溯相同长度后增1,继续比较。如果使用KMP算法,就不需要回溯。
KMP构造模式串T的模式函数next,构造方法:
在字符串S中查找模式串T,若S[m]!=T[n],那么T[n]的模式串函数next[n]告诉我们下一步应该比较哪两个字符:
结论:KMP方法在查询的时候,S不用回溯。
计算模式串
例1:T="abCabCad"
答案:next = [-1 0 0 -1 0 0 -1 4]
解答:
next[3] = -1的原因:(1)首先,T[3]==T[0]; (2)其次,k=1时T[2]!=T[0],k=2时T[1]+T[2]!=T[0]+T[1],即j前面的k个字符与开头k个字符不等。
next[6] = -1的原因:(1)T[6]==T[0]; (2)虽然j前面的3个字符与开头3个字符相等,但T[3]==T[6]
例2: T="AAAAAAAAAB"
答案:next=[-1 -1 -1 -1 -1 -1 -1 -1 -1 8]
解答:next[9] = 8告诉我们,当S[m]!=T[9]时,下次查询S[m]和T[8]
KMP(Knuth-Morris-Pratt)字符串模式匹配
原文:https://www.cnblogs.com/qionglouyuyu/p/13418955.html