引言
当我们需要统计一个模式串（Pattern）在主串（Text）中出现的次数时，我们最容易想到的是暴力算法。在最坏时间复杂度的情况下（如下图所示），
这个暴力算法的最坏时间复杂度达到了 O(mn)。这在 ICPC 和一些对时间复杂度有严格要求的题目当中是大概率无法通过的。所以本文将介绍一种由 Donald Knuth、Vaughan Pratt 和 James H. Morris 共同发明的 KMP 算法。
1. 人话理解 KMP 算法来源
我们依旧按照上面的例子，见下图，为了表示方便，我们将主串索引设为 i，子串的索引设为 j。
我们发现第一次循环当中，主串和子串索引在 0～1 是可以匹配上的，而在 i = 2, j = 2 的时候出现了失配。
而目前我们已知了 子串当中第一个字符（A）和第二个字符（B）不相同，而我们第一次循环情况可得到字符串和子串的第一个字符和第二个字符是可以匹配上的。
这说明了如果按照暴力算法，我们下一步（第二次循环，如下图）在首位一定是失配的。
按照 KMP 算法，我们按照其规则就直接'滑动'到了 i = 2, j = 0 进行新一轮的配对。算法将一直进行下去直到找到适配子串或未找到退出程序。
这样的好处就是将复杂度大幅减少，但是关于 KMP 算法如何实现，我们还需要从别的角度来思考。
2. KMP 思路讲解
我们的实现由两部分构成，第一个是决定 我们要滑动多长 的 next[] 数组的计算算法，第二个是主匹配 KMP 算法。
2.1 next 数组的构建 - '预知失配后的跳转位置'
为什么我们可以直接跳跃？ 想象一下，当我们发现第 6 位字符失配时，虽然主串和子串在这个位置不对应，但前面的 5 个字符是完全匹配的。 这意味着，虽然我们'此时此刻'不知道主串后面是什么，但我们通过子串本身的信息，就已经知道了主串刚刚经过了什么。 KMP 的精髓就在于：利用模式串（子串）自身的对称性，在失配时不要清零，而是回退到一个'即便右移依然能接得上'的位置。
我们先来看一个例子，对于相同的子串不同的主串的情况如下图：
