前言

我们中的大多数人从未真正学会 KMP 算法。市面上的大多数讲解要么迷失于复杂的记号，要么沉迷公式推导没能抓住本质。本文力争成为最后一篇 KMP 讲解。

需要的知识背景只有字符串的暴力匹配算法，我认为这个算法的难度等价于冒泡排序，因此大一的学生也能够看懂。

概念与记号

• $s[i..i+m-1]$：字符串 $s$ 中从 $s[i]$ 开始，长度为 $m$ 的一个子串。
• 前缀/后缀：字符串 $s$ 中的前/后 $x$ 个字符组成的子串，$0\leq x\leq n$，其中 $n$ 表示 $s$ 的长度。特别的，$x\neq n$ 时的前/后缀称为真前缀/真后缀。由于与原串相等的前缀在字符串匹配问题中没有讨论价值，所以下文中的前后缀均指真前后缀。
• 文本串与模式串：假如我们需要字符串 $s$ 中搜索 $p$，那么 $s$ 是文本串，$p$ 是模式串。

正文

在文本串中匹配模式串

首先，我们回顾 KMP 要解决的字符串匹配问题。

在文本串 $s$ 中找出模式串 $p$ 出现的所有位置。

令 $n$ 表示 $s$ 的长度，$m$ 表示 $p$ 的长度。容易想到 $O(nm)$¹ 的暴力做法，对 $s$ 的每一个位置 $i$，检查 $s[i..i+m-1]$ 是否等于 $p$。我们将这个过程称为一次 匹配。该算法的缺陷在于每次匹配都要回到 $p$ 的开头重新开始（称为 回退），这是不必要的。回退 的目的是重新尝试 $p$ 是否等于 $s$ 的下个子串，如果 $p$ 中有重复的部份，我们就可以将其利用以减少计算。

假设对当前位置 $i$，$s$ 的某个子串已经与 $p$ 的某个长度为 $x$ 的前缀匹配，下一个字符失配。那么就需要回退了。接下来考虑已经匹配的前缀 $t$，假如我们找到 $t$ 的 最长公共前后缀，长度为 $y$。由于 $s$ 的某个子串已经与 $t$ 匹配，即相等，那么回退到最长公共前缀结束的位置即可。

假如我们对模式串 $p$ 的每一个前缀都求出 最长公共前后缀，那么每次失配的时候，我们都可以回退到 最近 的可匹配位置。由于我们求的是 最长 的公共前后缀，那么它与 $s$ 匹配的长度最长，回退的距离也就越短。令所有前缀 $p[0..x]$ 的 最长公共前后缀 长度为 $\textit{next}[x]$。令 $i$ 和 $j$ 表示 $s$ 和 $p$ 当前匹配的位置，$s$ 与 $p$ 的匹配过程如下：

1. 如果 $s[i]$ 与 $p[j]$ 失配，那么 $j\leftarrow \textit{next}[j-1]$² 表示回退。重复这个过程，直到 $s[i]$ 与 $p[j]$ 匹配或者 $j$ 已经回退到开头。
2. 如果 $s[i]$ 与 $p[j]$ 匹配，$j\leftarrow j+1$ 表示匹配长度加 1。
3. 如果 $j$ 已到达末尾，则已发现了 $p$ 的一次匹配。

for (int i = 0, j = 0; i < n; i++) {
    while (j && s[i] != p[j])j = nxt[j - 1];
    if (s[i] == p[j])j++;
    if (j == m)cout << i + 1 - m << endl;
}

求解 $\textit{next}$ 数组

剩下的问题是：我们该如何求解 $p$ 的所有前缀 $p[0..x]$ 的 最长公共前后缀 的长度？其实，这个问题就等价于：

在 $p$ 的后缀中匹配前缀。

那么，这个问题就跟上面我们解决的在文本串中匹配模式串问题是一样的了。在实现中，我们常常写成将 $p$ 错开一位与自身匹配，其实这就是用一个前缀去匹配后缀。

for (int i = 1, j = 0; i < m; i++) {
    while (j && p[i] != p[j]) j = nxt[j - 1];
    if (p[i] == p[j]) j++;
    nxt[i] = j;
}

剩余的问题

等等，感觉有点怪？感觉 KMP 就像左脚踩右脚上天一样，对模式串和文本串进行一样的匹配操作，时间复杂度莫名其妙的就降低了？按照经验，这种类似递归的——自己调用自己的过程——应该不断缩小问题的范围。但匹配文本串和匹配模式串的问题范围应该是一样的，怎么就能得到 $\textit{next}$ 数组？这是因为 $\textit{next}$ 数组是递推得到的。

首先考虑暴力求解 $p$ 的所有前缀 $p[0..x]$ 的 最长公共前后缀 长度，即对于每一个前缀，判断它的每一个前后缀是否相同，时间复杂度 $O(n^3)$。注意到，随着长度增加，最长公共前后缀的长度是单调增加的，那么可以二分这个长度，时间复杂度 $O(n^2\log n)$。此时进一步的优化变得困难，我们考虑研究 $\textit{next}$ 数组本身的性质。可以发现，$\textit{next}[i] \leq \textit{next}[i-1]+1$，这提示了我们可以使用已有信息推导 $\textit{next}[i]$。另一点，目前的算法每次匹配前后缀时都回退到开头。KMP 算法中，由于发生失配时，我们会不断回退直到下一个字符匹配，所以不用进行字符串比较，而是比较两个字符即可，从而时间复杂度 $O(n)$。因此，KMP 的优化实际上是不断利用已有信息推导未知信息。

真题

即使理解了算法，也不一定会做题。一方面是考察的点往往与我们思考的过程不同，另一方面是真题的描述并不太清晰。09 年到 24 年 KMP 一共出现了三道真题，其中两道题类似且能够用前文的思想解决（所以只写一道），剩余一道题则引入了一个新的概念，下面就来看下如何解决。

2019 年第 9 题

设主串 T=“abaabaabcabaabc”，模式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是( )

这是比较典型的题目类型，为了避免错误，建议列表跟踪步数、变量 $i$，$j$ 以及字符 $T[i]$ 和 $S[j]$。

首先模拟得到模式串 $S$ 的 $\textit{next}$ 数组，然后进行匹配。可以发现在第 6 次比较时发生失配，根据 $\textit{next}$ 数组移动指针 $j$。$j = \textit{next}[5] = 2$，即 主串中的匹配位置不动，模式串向后移动，跳过等价的前后缀，进行下一步比较。

之后就能顺利完成匹配，答案是 $10$。

有没有快速的做法？我们发现，失配的位置是 $S[j] = c$，那么意味着前面的 “abaab” 都已经匹配。思考下一步比起从头开始，可以从哪里开始匹配？已匹配字符串 “abaab” 的最长公共前后缀是 “ab”，我们直接将前缀的 “ab” 移动到后缀 “ab” 的位置，然后从下一个字符 ‘a’ 开始匹配即可。

这就是熟练使用上文描述的 KMP 思想快速解题的思路，但可以发现很容易出错，所以仅供参考。

2024 年第 6 题

KMP 算法使用修正后的 next 数组进行模式匹配，模式串 S = “aabaab”，当主串中某字符与 S 中某字符失去配对时，S 将向右滑动的最长距离是( )

这道题涉及到了一个前面没有提及的概念：修正后的 $\textit{next}$ 数组，也被称为 $\textit{nextval}$。这其实并不是很常见的概念，因为它的优化仅仅局限于 模式串有大量重复字符 的情况。

其思想是：如果对于模式串 $p$ 中的一个字符 $p[j]$，$\textit{next}[j]$ 指向的那个字符 $p[\textit{next}[j]] = p[j]$，那么如果发生失配，$s[i] \neq p[j]$，仅把 $j$ 移动到 $\textit{next}[j]$ 后，下一次匹配 $s[i]$ 和 $p[\textit{next}[j]]$ 显然还会失配，那么我们可以修正 $\textit{next}$ 数组，再往前跳一次，即令 $\textit{next}[j]=\textit{next}[\textit{next}[j]]$。

简单来说：只要一个字符与它在 $\textit{next}$ 数组中所指的下一跳字符相同，就让 $\textit{next}$ 变成 $\textit{next}$ 的 $\textit{next}$。

if (i + 1 < m && p[i + 1] == p[j]){
    nxt[i] = (j ? nxt[j - 1] : 0);
}

可以发现，这个算法跟并查集的路径压缩思想是一样的，可以减少一些不必要的比较。

最后，这道题怎么做？首先，按照上述思想求出修正后的 $\textit{next}$ 数组，应为 [0, 0, 2, 0, 0, 2]。其次题目问最大滑动距离，等价于问 $j$ 与 $\textit{next}[j]$ 之间的最大差值，可以发现 $j = 5$ 时差最大，等于 $5$。

后话

KMP 之所以复杂，是因为它糅合了各种算法的思想。比如失配时的回退 while (j && s[i] != p[j])j = next[j - 1]，可以看到动态规划的影子，都是保存状态加速计算的思想，而重复跳转也有并查集的意味。又比如求 next 数组时，注意到前后缀匹配的问题与要解决的字符串匹配问题的等价。另外，对于字符串记号的复杂、模糊，也是增加理解难度的原因之一。还有臭名昭著的“差一问题”，下标从 0 和 1 开始的区别永远也搞不清，代码中一会 +1 一会 -1 仿佛魔法。

很多题解讲解 KMP 时，一开始能够把握住字符串匹配的思路，但后面讲怎么求 next 数组就飘了。也有的题解作纯粹的公式推导，最后得出结论。在我看来这就如同用代数运算去解释函数，无法把握本质。事实上，只要我们把握住 next 数组定义与解题思路，就不会走偏。这也引出了我近来思考的结论——对于个人学习来说，理解 > 公式 > 形式。