KMP 通俗讲解

Sving1024 · 2024-12-07 23:19:17 · 算法·理论

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

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

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

首先考虑暴力匹配的过程。

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

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

• $$\begin{align} S=&{\color{red}{\texttt{ab}}} {\color{yellow}\texttt{a}}{\color{red}{\texttt{aba}}}\texttt{abacbab}\\ T=&{\color{yellow}\texttt{a}}\texttt{baabacbab} \end{align}$$ 显然这种情况没什么用。因为这个匹配上的字串的长度甚至连原来匹配上的长度都比不上，最终自然不能匹配上整个 $T$。
• $$\begin{align} S=&{\color{red}{\texttt{aba}}}{\color{yellow}\texttt{aba}}\texttt{abacbab}\\ T=&{\color{yellow}\texttt{aba}}\texttt{abacbab} \end{align}$$ 这种情况是**有可能**匹配上整个串的，因为上一次匹配时就匹配到了第六个字符，因此程序处理到这里的时候也不知道后面能不能匹配上。 那么，这种字串有什么特点吗？ 注意到，由于这两个字串都匹配上了 $T$ 的某个前缀，因此这两个字串的前 $i(1\lt i \lt \min(|s1|,|s2|))$ 个字符是相等的。又因为 $s_2$ 同时也是 $s_1$ 的后缀，可以得到 $s_2$ 是 $s_1$ 的一段相等的前后缀（“Border“）。
• $$\begin{align} S=&{\color{red}{\texttt{abaaba}}}{\color{yellow}\texttt{aba}}\texttt{cbab}\\ T=&{\color{yellow}\texttt{aba}}\texttt{abacbab} \end{align}$$ 这种情况显然通过任何已知信息都无法推出了。

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

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

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

• 初始化：i\gets 0,k\gets0。
• 先暴力匹配。如果 S_{i+1}=T_{k+1}，则 k\gets k+1,i\gets i+1。
• 如果失配了，即 S_{i+k+1}\not=T_{k+1}，将 k\gets B_k，然后继续匹配。
• 如果 k=-1，直接令 i\gets i+1,k\gets0，相当于暴力匹配时失配的处理方式。
• 如果 k=|T|，说明找到了一个字串。如果还要寻找更多的字串，可以 k\gets B_k，然后继续匹配。
  这个过程的复杂度是 O(|S|)，证明可见 OI-Wiki。

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

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

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

因此 KMP 的总复杂度就是 O(|S|+|T|)。

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

全文完。

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

顺便，看看我的博客。