由 D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，简称KMP算法。
问题描述
由两个字符串 ms 和 s, 需要确认 s 是否存在于 ms 中，
如果存在，返回s的第一个字符在 ms的下标位置
朴素算法
使用双指针，i，j = 0, 分别指向 ms 和 s 的第一个字符，然后向后挨个对比
是否相等，若是遇到不相等的，则 i = 1, j = 0, 继续刚才的操作...
朴素算法缺陷与KMP算法优化思路
假设
ms: abazabcaed
s: abad
当 i = 3, j = 3 时
如果按照朴素的做法，得知 ms[3] != s[3] 后，会转而比较 ms[1] 和 s[0]，
主串和模式串的指针都回溯了。
其实没有必要，因为在这个时候，我们已经知道了两个字符串前3个字符是匹配的,如下：
012 3 45678
aba z abcad
aba d
因为 s[0] != s[1] , 所以 => ms[1] != s[0], 因此
我们可以直接跳过以 ms[1], s[0] 为起始的比较。
另外，由 s[0] == s[2]，所以 => s[0] == ms[2]
所以我们可以直接以 ms[2], s[0] 作为起始，开始新一轮的比较，
然而正因为已知 s[0] == ms[2], 可以直接当作比较过了，于是令 j = 1
如下：
012 3 45678
aba z abcad
a b ad
所以，i = 3 不变，只是 j 从 3 回溯到了 1，KMP的优化思路就是这样，
既避免了主串指针(i)的回溯，又跳过了模式串中一些不需要再比较的字符。
如果两个字符串是如下所示：
012 3 45678
abc z abcad
abc d
依然是 i=j=3 时，发现不匹配, 同样的：
s[0] != s[1]， => ms[1] != s[0]， => 跳过 ms[1], s[0] 作为起始的比较；
s[0] != s[2]， => ms[2] != s[0]， => 跳过 ms[2], s[0] 作为起始的比较；
所以我们直接进入 ms[3] 和 s[0] 作为起始的比较。
KMP引入
通过上面的例子，我们可以总结一下：
假设当前模式串在 j 处发现了不匹配， => s[0:j] 都是匹配的。
主串的指针(i) 不回溯，我们只考虑在新的一轮比较中，和此时ms[i]进行比较的 j=?
1、如果 s[0:j] 是如 abc 这样的，则说明下一个 j=1,2 都是不行的, j应该为0
2、如果 s[0:j] 是如 aba 这样的，则说明下一个 j 应该直接为 1；
3、如果 s[0:j] 是如 abac 这样的，则说明下一个 j=1,2,3 也都是不行的，j应该0
找规律，进一步总结：
模式串只有形如 aba、abjab 这样首尾有重合的，才可以跳过一些字符，假设这样重复的
字符数为 k, 即有 s[0:k] == s[j-k:j], 因此，新的一轮和ms[i]进行比较的 j = k。
所以关键就在于找 k 值，在 j 处发现不匹配时 k 值：
尝试手动找 k 值：
01234567
abaabcbc
j=0, => 第一个就不匹配，k = 0, i应该 +1, 从下面开始 i 都不变
j=1, => s[0:1] == ms[0:1], 这里字串只有1个字符，没有重合问题， k=0,
j=2, => s[0:2] == ms[0:2], 但没有重合, j = k = 0, i不变,
j=3, => a.a 重合，j = k = 1,
j=4, => a..a 重合，j = k = 1,
j=5, => ab.ab 重合，j = k = 2,
j=6, => 无重合，j = k = 0,
j=7, => 无重合，j = k = 0
所以，我们可以设计一个函数, 求 k 值，即 k = f(j)。
为了降低复杂度，可在匹配前，计算出所有 k，并缓存到 next 数组中
get_nexts 函数设计()
我们是需要找到每个j往左的字符串中（s[0:j+1]），重合的字符数。
定义 nexts 数组
方案一(自我实现):
1、已知nexts[0]=nexts[1] = 0, 因此，从 j = 2 开始。
2、一开始不知道有多少个重合，但是可能的最大重合个数是 (j + 1) // 2,
因此，需要先将 s[0:j+1] 拆解为两条字符串(得到 left_j, right_j),
让它们进行匹配，left_j: 作为模式串，right_j: 作为主串。
3、这个匹配过程中，依然可以应用kmp的思想，right_j 不回溯，
当发生失配时，left_j = nexts[left_j],
因为j是从底自上的, 所以每次失配都可以从 nexts 中拿到下一个 left_j (动态规划的子问题思想)。
4、最终当 right_j == j 时，重合数 = left_j + 1
def get_nexts1(s):
length = len(s)
nexts = [0] * length
for j in range(2, length):
left_j, right_j = 0, j // 2 + 1 if j % 2 else j // 2
while right_j < j:
if s[left_j] == s[right_j]:
if right_j + 1 < j:
left_j += 1
right_j += 1
elif left_j == 0:
right_j += 1
else:
left_j = nexts[left_j]
k = left_j + 1 if s[left_j] == s[j - 1] else 0
nexts[j] = k
return nexts
方案二(优化)：
方案一中进行了太多重复，没有必要的工作， 如
j = 7: abcdefg 对半分，需要从 a 和 e 开始比较, f,g 都不匹配，最终得到 nexts[7] = 0
j = 8: abcdefgh 还是从 a 和 e 开始比较，最终也得到 nexts[8] = 0
所以，不需要对每个j单独去对半分求解，可是不对半分，怎么能知道，某个 j下，字符串中有几个重合
字符呢？ 这其实已经又回到了最初的问题了， i 和 j都回溯了。 这里可以继续应用 kmp 思想。
让模式串应用kmp的思想，自己和自己匹配，需要求解的重合字符数，实际上就等于，失配时，next[j+1] + 1。
这里挺绕的，一层又一层的，来回顾一下：
主串(ms)： abcabaaaabaaacac
模式串(s)： abaabcbc
1、为了不像朴素那样 回溯主串指针 i, 通过 nexts[j] 获取下一个 j
2、我们知道 nexts[j] == "s[0:j+1]中前后重合字符数"
3、于是我们要得到s[0:j+1]中前后重合字符数
然后我们让模式串进行自我匹配
当 j + 1 处发生失配时，new_j = next[j+1]
于是得到 "s[0:j+1]中前后重合字符数" == new_j + 1
4、同样的，在自我匹配过程中，当 s[i] == s[j] 时，其实便说明了一点：
假设在 j + 1 处失配，那么 j + 1 就是我们要求的 重合字符数，
即 nexts[i+1] = j + 1
# 妈的，真 TM 绕...
def get_nexts2(s): # 自己匹配自己
length = len(s)
nexts = [0] * length
j, k = 1, 0
while j < length - 1:
if s[j] == s[k]: # 说明 倘若 j+1 处发现不匹配，s[0:k+1] 都是匹配的，
# 即，s[0:j+1] 中，s[0:k+1] 与 s[j-k:j+1] 是重合的
# 即，重合数是 k + 1
k += 1
j += 1
nexts[j] = k
elif k == 0:
j += 1
nexts[j] = k
else:
k = nexts[k]
return nexts
方案三(官方)；
def get_nexts(s): # 自己匹配自己
length = len(s)
nexts = [0] * length
j, k = 0, -1
nexts[j] = k
while j < length - 1:
if k == -1 or s[j] == s[k]:
# k == -1 , 说明 s[j] != s[0]
# s[j] == s[k]， 说明 倘若 j+1 处发现不匹配，s[0:k+1] 都是匹配的，
# 即，s[0:j+1] 中，s[0:k+1] 与 s[j-k:j+1] 是重合的
# 即，重合数是 k + 1
k += 1
j += 1
nexts[j] = k
else:
k = nexts[k]
return nexts
KMP匹配算法
def kmp_match(ms, s):
i, j, m_len, s_len = 0, 0, len(ms), len(s)
nexts = get_nexts(s)
while i < m_len:
if j == -1 or ms[i] == s[j]:
if j != s_len - 1:
i += 1
j += 1
else:
return i - j
else:
j = nexts[j]
return -1