2021 年就学了KMP，2023写一篇详细点的总结。
首先我们需要理解朴素做法。
- 枚举开始匹配的位置 \(i\)，和匹配串中的每个位置逐一匹配，失败就停止移动继续匹配，最坏情况复杂度高达 \(O(mn)\)
上述做法的缺陷就在于没有充分利用信息，比如匹配失败时就从头开始。我们考虑一次匹配中，如果失败了，那么至少需要移动多少，首先贴一张图。
如上图所示，蓝色的线段表示文本串，红色的串表示模式串，竖着的绿线表示在某次匹配中，竖线及其之前的所有位置均已匹配成功，红圈和绿圈的两个位置为第一次匹配的失败位置。那匹配之后至少要移动多少呢，假设是最下面红色线段的位置，那么画橙圈的部分必然的部分必然全等，而因为两个红色的是平移构造而成的，所以对应位置全等，所以本质上就是前缀和后缀相等。而为了求出最少移动距离就可以转换为最大前后缀长度。接下来就是求这个最长公共前后缀的问题了。这个求解方式其实和上述的匹配过程基本一致，还是以图为例。用 \(ne_i\) 表示匹配到 \(i\) 的结果。
上图中我们已经求好了位置 \(i\) 之前的所有答案，现在想要推出后面的，由于前面的位置相等，其实还是一样的方法就行了。