AKira Lau

1.1 朴素匹配算法的缺陷#

在朴素匹配算法的匹配过程中，我们分别用指针 i 和指针 j 指示文本串 T 和模式串 p 中当前正在对比的字符。当发现文本串 T 的某个字符与模式串 p 不匹配的时候，j 回退到开始位置，i 回退到之前匹配开始位置的下一个位置上，然后开启新一轮的匹配，如图所示。

图1-1：朴素匹配算法示意图（失配时 i 回退、j 归 0，从头重新匹配）

这样，在 Brute Force 算法中，如果从文本串 T[i] 开始的这一趟字符串比较失败了，算法会直接开始尝试从 T[i + 1] 开始比较。如果 i 已经比较到了后边位置，则该操作相当于将指针 i 进行了回退操作。

那么有没有哪种算法，可以让 i 不发生回退，一直向右移动呢？

1.2 KMP 算法的改进#

如果我们可以通过每一次的失配而得到一些「信息」，并且这些「信息」可以帮助我们跳过那些不可能匹配成功的位置，那么我们就能大大减少模式串与文本串的匹配次数，从而达到快速匹配的目的。

每一次失配所告诉我们的信息是：主串的某一个子串等于模式串的某一个前缀。

这个信息的意思是：如果文本串 T[i: i + m] 与模式串 p 的失配是下标位置 j 上发生的，那么文本串 T 从下标位置 i 开始连续的 j - 1 个字符，一定与模式串 p 的前 j - 1 个字符一模一样。

以刚才图中的例子来说，文本串的子串与模式串 p 的失配是在第 5 个位置发生的，那么：

文本串 T 从下标位置 i 开始连续的 5 个字符，一定与模式串 p 的前 5 个字符一模一样，即 "ABCAB" == "ABCAB"。

• 而模式串的前 5 个字符中，前 2 位前缀和后 2 位后缀又是相同的，即 "AB" == "AB"。

所以根据上面的信息，我们可以推出：文本串子串的后 2 位后缀和模式串子串的前 2 位是相同的，即这部分是之前已经比较过的，不需要再比较了，可以直接跳过。 那么我们就可以将文本串中的失配字符直接对准模式串中对应前缀的下一个字符，继续进行对比。这样 i 就不再需要回退了，可以一直向右移动匹配下去。在这个过程中，我们只需要将模式串 j 进行回退操作即可。

KMP 匹配算法

KMP 算法就是使用了这样的思路，对模式串 p 进行了预处理，计算出一个「部分匹配表」，用一个数组 next 来记录。然后在每次失配发生时，不回退文本串的指针 i，而是根据「部分匹配表」来决定模式串可以向右移动的位数。

3.1 概念与人为规定#

next[j] 代表模式串 0 到 j - 1 这段子串的最长公共前后缀的长度。也就是说，next[j] 记录的是：模式串第 j 个字符之前的子串中，最长相等的前缀与后缀的长度。

人为规定：next[0] = -1（因为 0 之前没有子串），next[1] = 0（因为只有一个字符时，真前缀集合为空）。

注意：有些题目或教材（如严蔚敏版《数据结构》）里的 next 数组下标从 1 开始，此时人为规定 next[1] = 0。两种写法本质相同：从 1 开始的数组，就是从 0 开始的数组整体加 1（下标同步平移），见 3.2 的对照表。做题前必须看清题目用的是哪一种约定。

3.2 两种 next 数组约定（重点）#

「从 0 开始」和「从 1 开始」是两种常见的 next 数组写法，它们的本质含义相同，只是下标起点和数值相差 1。下面讲清楚两者的区别。

对照关系举例："abaabac" 中，约定一的 next0[5] = 2，约定二的 next1[6] = 3 = 2 + 1。整体平移后，约定二的 next1[j] 从 0 开始的数组各元素 +1 即可得到，例如 [-1, 0, 0, ...] → [0, 1, 1, ...]。

next 数组的长度等于模式串长度 m：匹配过程中失配时 i2 最大只到 m - 1，用到的 next[i2] 下标都在 0..m-1 范围内，因此不需要求 next[m]。

为什么会有这两种写法？约定一（从 0 开始）配合 0 下标数组直接用，写代码最自然；约定二（从 1 开始）常见于教材（如严蔚敏版《数据结构》）中用 1 下标表示的串。两者在匹配时失配跳转的公式不同（一个是 i2 = next[i2]，一个是 j = next[j]），但只要和对应的匹配代码配套使用，结果完全一致。

3.3 手算 next 数组#

以模式串 "abaabac" 为例，逐位手算 next 数组（采用约定一，下标从 0 开始）：

手算方法：对每个 j，只看模式串的前 j 个字符（下标 0 到 j - 1），找到它们的最长公共前后缀长度即可。例如 j = 5 时子串为 "abaab"，前缀与后缀最长相等的是 "ab"，所以 next[5] = 2。其中 next[0] = -1、next[1] = 0 是人为规定：0 之前没有子串，而只有一个字符时其前缀集合为空。

3.4 递推计算 next 数组#

手算理解含义，但代码要用递推。递推过程中用一个变量 cn 记录「当前前缀的长度信息」（即 next[i-1]），从 i = 2 开始填表。递推规则只有三条：

• ① 相等分支：若 ms[i-1] == ms[cn]，则 next[i] = cn + 1，i、cn 同时前进（等价写法：next[i++] = ++cn）。
• ② 回退分支：若不等且 cn > 0，则 cn = next[cn]（cn 往前跳，跳到更短的前缀继续比）。
• ③ 结束分支：若 cn 已经跳不动了（cn == 0 且仍不等），则 next[i] = 0，i 前进。

1
// 递推计算 next 数组（约定一：next[0] = -1，next[1] = 0）
2
int i = 2;   // 当前要填 next[i] 的位置
3
int cn = 0;  // 前缀长度信息，等价于 next[i-1]
4
while (i < ms.length) {
5
    if (ms[i-1] == ms[cn]) {          // ① 相等：i 处信息 = cn + 1
6
        next[i] = cn + 1;
7
        i++;
8
        cn = next[i-1];               // 等价于 ++cn
9
    } else if (cn > 0) {              // ② 不等且还能跳：cn 回退到 next[cn]
10
        cn = next[cn];
11
    } else {                          // ③ 跳不动：next[i] = 0
12
        next[i] = 0;
13
    }
14
}

回退的本质：当 i-1 处字符与 cn 处字符不等时，说明以当前前缀长度无法延伸，就退而求其次，去尝试更短的前缀——而“更短的候选”恰好就是 next[cn]（最长公共前后缀的前缀部分）。

为什么递推的复杂度是 $O(M)$？因为 i 最多前进 M 次，cn 最多回退 M 次，总体是常数倍的操作次数。

6.1 优化思路：找出「跳过去还是失配」的坑#

先看一个具体例子：模式串 $p =$ "aaaabab"，主串为 "aaaacaaaab"。匹配到主串第 4 个字符 c 时失配，此时 $j = 4$（模式串指向第 5 个字符「a」）。按照 next 数组跳转：

• next[4] = 3，跳到 $j = 3$：p[3] = 「a」，和失配字符（主串的 c）不一样？——不对，仔细看：

注意：失配发生在 p[j] 与主串字符比较时。若 p[j] == p[next[j]]，那么跳到 next[j] 后，主串那个字符仍然不匹配，又会失配一次，然后又要跳到 next[next[j]]...

• 主串字符是 c，p 全是 a，所以无论 j 跳到哪，只要 p[j] == 「a」，就必然再次失配。

优化思路：与其跳到一个「已知字符相同、必然再次失配」的位置，不如一次跳到「字符真正不同」的位置（或者直接跳无可跳）。把这种压缩后的跳转表叫做 nextval。

6.2 怎么计算：手算 nextval#

手算规则一句话：nextval[j] = next[j]，但若 p[j] == p[next[j]]，则 nextval[j] = nextval[next[j]]。也就是说：看 next 跳过去的那个字符和当前失配字符是否相同，相同就继续向前压缩（取 nextval），不同就直接用 next。

仍以 "abaabacc" 为例，next = [-1, 0, 0, 1, 1, 2, 0, 1]，逐位计算 nextval：

对照结论：nextval = [-1, 0, -1, 1, 0, 2, -1, 1]。可以看到 $j = 2$、4、6 三处的值被压缩了：因为跳过去的字符和失配字符相同（都是 a/b/a），干脆再往前取。

6.3 递推计算 nextval（O(M)）#

递推时并不需要先求完 next 再求 nextval，可以一遍递推同时得到 next 与 nextval：

1
// 求模式串 ms 的 next 与 nextval（约定一：next[0] = -1）
2
vector<int> getNextValArray(const string& ms) {
3
    int m = ms.size();
4
    if (m == 0) return {};
5
    vector<int> next(m);
6
    int i = 0, cn = -1; // cn 初始为 -1（对应 next[0]）
7
    next[0] = -1;
8
    // 原文此处代码不完整
9
}

这个写法直接产出 nextval（因为 ms[i] != ms[cn] 时存 cn，相同则存 nxt[cn]）。如果把关键行改成 nxt[i] = cn，得到的就是普通 next 数组。

复杂度同样是 $O(M)$：i 最多前进 M 次，cn 最多回退 M 次。

6.4 匹配阶段怎么用 nextval#

匹配代码几乎不用改，只需把失配分支的跳转数组换成 nextval：

1
// 匹配阶段：仅将 i2 = next[i2] 换成 i2 = nextval[i2]
2
} else {
3
    i2 = nextval[i2]; // 一跳到位，避免重复失配
4
}

好处：最坏情况下（如 "aaaaab" 这种大量相同字符的模式串），nextval 让跳转一步到位，匹配过程从「可能多次回退」变成「几乎不回退」，常数因子更小。复杂度量级不变（仍为 $O(N + M)$），但实际速度更快。

6.5 next 与 nextval 对比#

nextval 是 next 的「压缩版」：跳过去的字符如果和失配字符相同，就继续往前压缩，直到字符不同或跳无可跳为止。