给定一个长度为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