KMP算法笔记II ----- 学会计算next数组
第一次学习KMP算法走了不少弯路，下面老高按照自己的学习步骤，总结一下KMP算法的要点，如果有错误或者疑问，欢迎指正！
老高使用python语言实现算法，实现的语言不重要，重要的是他的思想！(其实老高的C语言早已年久失修?)
本文是系列的第二篇，主要探讨一下KMP算法的思维方式并引出next数组概念。
一些约定
- 函数查找不到返回-1，最好支持全局搜索
- s(string) 代表 需要匹配的字符串
- t(target) 代表 我们想要查找的字符串
- i 代表查找string时的下标
- j 代表匹配target时的下标
- k 代表next数组时最大前缀后缀的长度
- next(next) 代表 next数组
理解KMP算法
通过第一篇，我们知道用笨办法查找字符串，现在我们通过一些特例来了解KMP算法。相比于朴素算法，KMP优化了j的移动策略，使得在发生失配的时候不需要再把i向左移动了，从而减少了匹配次数，大大提高了匹配效率。KMP算法的难点在于求解NEXT数组，NEXT数组就像是一本字典，它会指引你在发生失配的时候需要做什么。
现在我们考虑在某个字符串搜索字符ABABC，下面演示一下
A B A B Å B C
A B A B C
KMP算法的不同就在于箭头处出现失配的做法，下面看看朴素算法的下一步：
A B A B Å B C
A B A B C
同时对比KMP算法的下一步：
A B A B Å B C
A B A B C
快来找不同：
- 朴素算法的游标发生倒退，而KMP算法没有
- 重新对比的位置很奇特，为什么不是从头开始呢
我们先观察ABABC字符串，发现有ABAB这个模式，所以当我们匹配到第五个字母A发生失配时，就不用从头开始计算，而直接从ABABC的第三位开始对比，字面下的意思就是最近的AB我对比不成，但是我又发现后面的AB有一个远方亲戚，即最前方的AB可以直接用来匹配，而不用去管之前的匹配，确实省了不少事情。
接下来要确定的就是如何计算next数组了，其实就是求解当前字符处（或之前）的字符串的最大前缀后缀的共有最大元素的长度。
在此老高得到了很多算法，但是最后生成的数组不尽相同。
比如 阮一峰的网络日志- 字符串匹配的KMP算法中，next[k]的计算包含当前k对应字符，即ABABC的next[3]的值的是ABAB的计算结果。
即 ABABC的next数组为[0, 0, 1, 2, 0]
而另一种结果为[-1, 0, 0, 1, 2]，此结果指的是k之前的字符串所计算的值，与前者差别不大，也就是next[j-1]和next[j]的问题。
下面我们笨办法试着写一个生成next数组(包含当前字符)的方法吧！
# 此方法还可以优化，比如去掉t_temp
def get_next_slow(t):
t_len = len(t)
# 初始化next数组
next_list = [0] * t_len
# 除了i=0，其他都需要计算
for i in range(1, t_len):
# 初始化max_len
k = 0
# 截取需要计算的部分
t_temp = t[:i + 1]
# j表示当前最大匹配长度，如果对比成功，j就是k
j = i
while j > 0:
# 一步一步截取前缀，直到j=0
if t_temp[0:j] == t_temp[i - j + 1:]:
# 如果相等，直接赋值
k = j
break
j = j - 1
# 将max写入next
next_list[i] = k
return next_list
或者使用递归思想，模式字符串记为P(下标从0开始)，next[q] = k 表示P[q]之前的子串中，存在长度为k的相同前缀和后缀，即P[0]~P[k-1]与P[q-k]~P[q-1]依次相同。如果P[k] = P[q]，那么next[q+1] = k+1，此时表示P[q+1]之前的子串中，存在长度为k+1的相同前后缀，这应该不成问题。（转自知乎>怎么理解kmp算法中的next数组?）
def get_next(t):
t_len = len(t)
next = [0] * t_len
k = 0
for i in range(1, t_len):
# 进入循环查找是否存在一个k，使得t[i] == t[k]，k会原来越短，直到k=0，退出循环
# 注：i是不变的
while k > 0 and t[i] != t[k]:
k = next[k - 1]
# 如果t[i] == t[k]，k长度加一
if t[i] == t[k]:
k = k + 1
next[i] = k
return next