给定一个长度为n的主字符串str和一个长度为m的pattern（如str = 'qwertyuiopasdfghjkl'，pattern = 'yuiop'），需要从str中找到被pattern命中的子串，你怎么做？
最简单的做法：BF算法
BF是bruteforce的缩写，暴力算法，事实上这根本不能称之为一个算法，基本思想就是【逐个检查字符是否匹配，不匹配则将pattern后移一个字符位置然后继续检查】。每次不匹配只后移动一个字符位置，做了很多无谓的比较，太慢了，时间复杂度O(n*m)
改进算法：KMP算法
先说结论，KMP算法相比BF算法的改进之处在于，每次移动都直接移动到下一个能够匹配pattern的起始字符的位置，【跳步移动】而不是一个一个字符地移动+【不总是从首个字符开始比较，减少了无谓的比较】。时间复杂度O(n+m)
1.KMP算法的基本思想——【后缀变前缀】：
以
主字符串"ababadababacambabacaddababacasdsd"（其中的斜体部分是匹配部分）
pattern串"ababaca"
为例
-
确定match_s。记主字符串str中和模式pattern已匹配的前缀串为match_s，【KMP的一切都基于这个match_s】
如，最开始时，主字符串中的已匹配的前缀串match_s为"ababa" -
寻找最长前后缀。从match_s中找出最长的相等前后缀prefix and suffix
如，match_s为"ababa"时，prefix(前3个字符) = "aba" = suffix(后3个字符) - 后缀变前缀。利用prefix和suffix相等的关系，将pattern从prefix位置移动至suffix位置，开始下一次匹配过程
完整的用例过程如下：
- 主字符串str和模式pattern首次尝试匹配时，前5个字符匹配，得到match_s为"ababa"；
- match_s为"ababa"时，prefix(前3个字符) = "aba" = suffix(后3个字符)
- 后缀变前缀。模式pattern向右移动2个字符单位，使得pattern新的起始位置与suffix重合，开始下一次匹配过程
2.利用next数组做到后缀变前缀
通过刚才的例子，pattern向右移动2个字符单位，可以使得pattern新的起始位置与suffix重合。那么这个2怎么得来的呢？
很简单
match_s = "ababa"，
suffix = "aba"，len(match_s) - len(suffix) = steps => 5 - 3 = 2
因此，只需要得到match_s和最长前后缀就可以计算steps
一般地，使用一个长度为【m+1】的一维数组next存储match_s和最长前后缀信息，next的下标表示match_s的长度，存储的值表示最长(前)后缀的长度
对于pattern = "ababaca"，match_s可以是'', 'a', 'ab', 'aba', 'abab', 'ababa', 'ababac', 共7个，因此对应next数组的长度为7
然后再把所有的match_s的最长(前)后缀的长度填入数组就大功告成
可以看到，next数组只与pattern有关，而与str无关
KMP算法之next数组
【重点】next数组的填充，可以通过动态规划实现
- 显然，next[0]和next[1]直接就是0。也就是说，next这个dp数组的初始状态是已知的，只需要自底向上通过状态转移方程填满next数组后面的空位就O了
- 对于next[i]（i >= 2），有：next[i]对应的match_s = next[i-1]对应的match_s + pattern[i-1]。那么显然也有，next[i]对应match_s的可能最长后缀suffix = next[i-1]对应的match_s的最长后缀 + pattern[i-1]，如，'abab'的可能最长后缀 = 'aba'的最长后缀'a' + 'b' = 'ab'；那么我们要验证'ab'这个可能的最长后缀到底是不是真的最长后缀。
令prefix_len = next[i-1]- 如果pattern[i-1] == pattern[prefix_len]（prefix_len的值正好标记了对应的match_s最长前缀的下一位置），即后缀上增加的字符 = 前缀上增加的字符，则next[i] = next[i-1] + 1
- 如果pattern[i-1] != pattern[prefix_len]，即后缀上增加的字符 != 前缀上增加的字符，那么next[i] 就不能与 next[i-1] 建立起转移关系，怎么办？事实上，next[i] 还可以尝试与 next[i-1]之前的元素建立联系。例如，我们可以把计算'ABCA|ABCA|B'最长前后缀的问题，转换成计算'ABCA|B'最长前后缀的问题，就是把pattern【截断一截】，这样一来next[9] = next[next[prefix_len]] + 1 = next[4] + 1 = 1 + 1 = 2。如果截断一次仍然不能建立联系，那就2次
计算next数组的代码如下：
def getNextArray(pattern):
# 创建next数组
next_array = [0 for i in range(len(pattern))]
prefix_len = 0
# 开始填充next_array数组
for i in range(2, len(pattern)):
# 上一前缀长度
prefix_len = next[prefix_len]
# 加上prefix_len != 0是为了保证while能够正确结束，避免一直存在pattern[i] != pattern[prefix_len]产生死循环
while pattern[i] != pattern[prefix_len] and prefix_len != 0:
# 截断pattern，更新截断后上一前缀的长度
prefix_len = next[prefix_len]
if pattern[i] == pattern[prefix_len]:
prefix_len += 1
# 填充next_array[i]
next_array[i] = prefix_len
