KMP 通俗讲解

本文原计划于 国庆发布。 最近有点颓，写不动题目了，来水一篇博客。

KMP 是 Knuth–Morris–Pratt 算法的简称，由 Knuth、Pratt 和 Morris 在 1977 年共同发布。该算法用来处理字符串匹配的问题（就是给定一个字符串，求它的所有字串中另一个字符串相等的字符串）。

网上有很多讲解 kmp 的文章了，但其实 kmp 有着（自认为）更简单的理解方法。本文记文本串为 ，模式串为 。

首先考虑暴力匹配的过程。 如图， 匹配上了 的一个字串。当匹配到下一个字符的时候，你会发现下一个字符不等了，这种情况成为失配。此时暴力方法会将头指针向后移一位，然后重复上述的过程。但是，难道已经匹配上的这些字符串不能给我们提供一些额外的信息了吗？

考虑下一个可以和 匹配上的 的字串。将前一个匹配上的字串记为 ，将新匹配的字串记作 。

• 在 内开始，在 结束。 显然这种情况没什么用。因为这个匹配上的字串的长度甚至连原来匹配上的长度都比不上，最终自然不能匹配上整个 。
• 在 内开始，一直延伸到 的末尾（其实就是说 为 的后缀）。 这种情况是有可能匹配上整个串的，因为上一次匹配时就匹配到了第六个字符，因此程序处理到这里的时候也不止到后面能不能匹配上。
  那么，这种字串有什么特点吗？
  注意到，由于这两个字串都匹配上了 的某个前缀，因此这两个字串的前 个字符是相等的。又因为 同时也是 的后缀，可以得到 是 的一段相等的前后缀（“Border“）。
• 在 外， 这种情况显然通过任何已知信息都无法推出了。

由上述分类可以发现，下一个可能匹配上的位置只和已经匹配上的字符串有关。由于这个字符串必然是模式串的某个前缀，我们可以预处理模式串的所有前缀的 Border。但是那么多 Border，选哪一个呢？容易发现，选择最长的 Border 可以保证不漏。因为加入选择较短的 Border，如果较长的 Border 合法，则不能再次回到较长的 Border，因为每次指针都会向后面移动。而如果较短的 Border 合法，必然可以通过上述方法得到。因此我们只需要预处理出模板串的最长 Border 即可。

先假设求出了最长的 Border，我们又该怎么做呢？

首先，令一个指针 指向 中匹配上的字符串的末尾，令已经匹配上的字符串长度为 ， 的长度为 的前缀的最长 Border 对应的前缀的末尾的位置为 （没有 Border 则为 ）。

• 初始化：。
• 先暴力匹配。如果 ，则 。
• 如果失配了，即 ，将 ，然后继续匹配。
• 如果 ，直接令 ，相当于暴力匹配时失配的处理方式。
• 如果 ，说明找到了一个字串。如果还要寻找更多的字串，可以 ，然后继续匹配。
  这个过程的复杂度是 ，证明可见 OI-Wiki。

我们在暴力匹配是，将 自增前，将上面这个 匹配到的最远的 记录下来。显然由于 单调递增，且每次增加 ，每个 都会有一个对应的 。并且我们只增加了 次 的操作，因此不会增加复杂度。

考虑这个东西的实际意义，应该是代表 的长度为 的前缀的后缀和 的前缀可以匹配到的最远距离。欸，我们发现这个东西和 Border 的定义很像。 每个位置的 Border 不就是 的长度为 的前缀的后缀和 的前缀匹配的最长距离吗（显然，这个前缀的长度并不会超过 ——我们可以放心的将“和 的长度为 前缀匹配的最长距离吗”替换为“和 的前缀匹配的最长距离”）？我们发挥想象力，将上面这个过程中的 全部换成 ，会发生什么？

我们将初始化改成 ，假设现在正在匹配第 个字符，显然此时有 （显然，你匹配上的字符串不能比其中一个字符串还长）。那么，假设此时失配了，就需要令 ，而这个 小于 ，因此， 在前面已经求出！这样改变程序，不但可以正常运行，甚至还可以帮我们正常求出 Border（这就其他地方可以看到的“求 Border 相当于对自己匹配”的意思）！类似匹配的复杂度，求 Border 的复杂度就是 。

因此 KMP 的总复杂度就是 。

代码：网上太多了，因此就不给了。

全文完。

---

讲个笑话，我自己至今还没写过 KMP 的模板。