KMP 通俗讲解
本文原计划于 \(2024\) 国庆发布。
最近有点颓，写不动题目了，来水一篇博客。
KMP 是 Knuth–Morris–Pratt 算法的简称，由 Knuth、Pratt 和 Morris 在 1977 年共同发布。该算法用来处理字符串匹配的问题（就是给定一个字符串，求它的所有字串中另一个字符串相等的字符串）。
网上有很多讲解 kmp 的文章了，但其实 kmp 有着（自认为）更简单的理解方法。本文记文本串为 \(S\)，模式串为 \(T\)。
首先考虑暴力匹配的过程。 \[ \displaylines{ S=&{\color{red}{\texttt{abaaba}}}\texttt{abacbab}\\ T=&{\color{blue}\texttt{abaaba}}\texttt{cbab} } \]如图，\(T\) 匹配上了 \(S\) 的一个字串。当匹配到下一个字符的时候，你会发现下一个字符不等了，这种情况成为失配。此时暴力方法会将头指针向后移一位，然后重复上述的过程。但是，难道已经匹配上的这些字符串不能给我们提供一些额外的信息了吗？
考虑下一个可以和 \(T\) 匹配上的 \(S\) 的字串。将前一个匹配上的字串记为 \(s_1\)，将新匹配的字串记作 \(s_2\)。
- \(s_2\) 在 \(s_1\) 内开始，在 \(s_1\) 结束。 \[\displaylines{ S=&{\color{red}{\texttt{ab}}}{\color{yellow}\texttt{a}}{\color{red}{\texttt{aba}}}\texttt{abacbab}\\ T=&{\color{yellow}\texttt{a}}\texttt{baabacbab} }\] 显然这种情况没什么用。因为这个匹配上的字串的长度甚至连原来匹配上的长度都比不上，最终自然不能匹配上整个 \(T\)。
- \(s_2\) 在 \(s_1\) 内开始，一直延伸到 \(s_1\) 的末尾（其实就是说 \(s_2\) 为 \(s_1\) 的后缀）。\[\displaylines{
S=&{\color{red}{\texttt{aba}}}{\color{yellow}\texttt{aba}}\texttt{abacbab}\\
T=&{\color{yellow}\texttt{aba}}\texttt{abacbab}
}\]
这种情况是有可能匹配上整个串的，因为上一次匹配时就匹配到了第六个字符，因此程序处理到这里的时候也不止到后面能不能匹配上。
那么，这种字串有什么特点吗？
注意到，由于这两个字串都匹配上了 \(T\) 的某个前缀，因此这两个字串的前 \(i(1\lt i \lt \min(|s1|,|s2|))\) 个字符是相等的。又因为 \(s_2\) 同时也是 \(s_1\) 的后缀，可以得到 \(s_2\) 是 \(s_1\) 的一段相等的前后缀（“Border“）。 - \(s_2\) 在 \(s_1\) 外，\[\displaylines{ S=&{\color{red}{\texttt{abaaba}}}{\color{yellow}\texttt{aba}}\texttt{cbab}\\ T=&{\color{yellow}\texttt{aba}}\texttt{abacbab} }\] 这种情况显然通过任何已知信息都无法推出了。
由上述分类可以发现，下一个可能匹配上的位置只和已经匹配上的字符串有关。由于这个字符串必然是模式串的某个前缀，我们可以预处理模式串的所有前缀的 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 的模板。 