KMP全称是Knuth–Morris–Pratt algorithm，用O(m + n)的时间复杂度从字符串s中找到匹配串p.
此外还可以与Trie结合(AC自动机)用于解决多模式匹配问题。
KMP的核心思想是如果s[i] != p[j], 那么j快速回到k使得s[i+k:i-1] 和 p[:k]保持一样。如果s[i] != p[k]那么继续回退。这么做实际上是通过调整j在p的位置以高效利用在i和j之前s和p 匹配上的部分
如何给 p 记录前面匹配的部分呢？自己和自己对比
kmp = [0] * len(p)
curr_match_len = 0
for i, c in enumerate(p):
while curr_match_len != 0 and c != p[curr_match_len]:
curr_match_len = p[curr_match_len - 1]
if c == p[curr_match_len]:
curr_match_len += 1
p[i] = curr_match_len