KMP算法复习
太久没打了，刚好有道题用上了，就复习一下。 我觉得复到KMP应该就够用了，如果要AC自动机我直接死在那里。
参考资料 如何更好地理解和掌握 KMP 算法? - 阮行止的回答 - 知乎 https://www.zhihu.com/question/21923021/answer/1032665486
核心思想
KMP算法要解决的问题是字符串匹配问题。给定原串S和模版串P，求解原串中是否存在子字符串与模版串相匹配。
最简单的想法就是暴力搜索，设原串S长度为n，模板串P长度为m，显然暴力的时间复杂度为O(nm)，非常慢。
KMP的想法是充分利用适配信息，其next数组的定义如下：next[i]表示在P[0:i]子串中，使前k个字符恰好等于后k个字符的最大的k，且k不能等于i+1（否则就等于它自己了） 这个数组的定义挺绕的，第一眼基本都不会反应过来，我就不插图了，只用文本表述一下（建议看图）。KMP的失配匹配，本质上就是把模版串向前伸，直到伸到前缀与后缀匹配为止，这实际上就是自己与自己匹配。因此这个k就是前缀与后缀相同的最大长度k。
因此next数组可以用如下方法求得
def getNxt(x):
for i in range(x,0,-1):
if p[0:i] == p[x-i+1:x+1]:
return i
return 0
nxt = [getNxt(x) for x in range(len(p))]构建next数组的复杂度显然是O(m^2)的 使用next数组加速匹配
def search(p,s):
tar = 0 # 主串中将要匹配的位置
pos = 0 # 子串中将要匹配的位置
while tar < len(s):
if s[tar] == p[pos]: # 若两个字符相同，匹配成功，tar和pos各进一步
tar += 1
pos += 1
elif pos>0: # 失配，且pos>0，则next数组移动
pos = nxt[pos-1]
else: # pos[0]也失配了，则主串前进
tar += 1
if pos == len(p): # pos走到了len(p)，匹配成功
print(tar-pos) # 输出起始地点
pos = nxt[pos-1] # 当作失配，继续下一次匹配时间复杂度为O(n+m)，会比暴力方法小很多。
快速求next数组
这一步也是KMP的精髓，前面我没记错的话应该是MP算法，这一步是K算法。 其核心在于让P自己与自己做匹配。
next数组的定义是使得前缀与后缀的前k个字符相等的最大的k，隐含着一个匹配。因此可以考虑使用next数组递归求解自身
现在考虑两种情况，对于给定字符串
a b c a b d d d a b c a b c
_________ X ----__________X
0 0 0 1 2 0 0 0 1 2 3 4 5 ?前一个子串为A串，后一个子串为B串在两个X的地方。如果前者等于后者，则？处的next显然等于6，即next[i-1]+1，即得配的情况。 但是现在是失配了，显然目标是要找到一个新的now，使得前面的前缀与后面的后缀相同，而且注意到前面的A串与B串是相同的，因此就可以利用起A串的next数组。
nxt = []
def buildNxt():
nxt.append(0) # next[0]一定是0
x = 1 #求解从1开始
now = 0
while x < len(p):
if p[now] = p[x]: #第一种情况，得配，相前一位
now += 1
x += 1
nxt.append(now) # 之前没有，我看了一下意思，我觉得要加上
elif now>0: # 失配，需要缩小now
now = nxt[now-1]
else:
nxt.append(0) #now最小，此时肯定为0
x += 1腾讯云开发者
