def KMP(s, p):
nex = getNext(p)
i, j = 0, 0 # 分别是s和p的指针
while i < len(s) and j < len(p):
if j == -1 or s[i] == p[j]: # j==-1是由于j=next[j]产生
i += 1
j += 1
else:
j = nex[j]
if j == len(p): # 匹配到了
return i - j
else:
return -1
def getNext(p):
nex = [0] * len(p)
nex[0] = -1
i = 0
j = -1
while i < len(p) - 1: # len(p)-1防止越界，因为nex前面插入了-1
if j == -1 or p[i] == p[j]:
i += 1
j += 1
nex[i] = j # 这是最大的不同：记录next[i]
else:
j = nex[j]
return nex
- 参考文献
1.B站灯笼哥
2.KMP算法python实现
3.如何更好的理解和掌握 KMP 算法?
