世界的尽头

KMP 算法

字符串匹配问题中，给定一个长文本 s 和一个模式串 p，需要找出 p 在 s 中出现的所有位置。

朴素做法会从长文本的每个位置重新开始比较。当已经匹配了很多字符却在后面失配时，前面的比较结果就被全部丢弃，最坏时间复杂度为 $O(nm)$ 。

KMP 的核心思想是：长文本指针不回退，失配时利用已经匹配的内容，将模式串移动到下一个可能匹配的位置。这个“下一个位置”由 next 数组记录。

本文采用与 AcWing 模板一致的 1-based 下标：

s[1..n] 是长文本，长度为 $n$ ；
p[1..m] 是模式串，长度为 $m$ ；
代码中将 next 数组简写为 ne。

前缀、后缀与 `next` 数组

对于一个字符串：

前缀：必须从第一个字符开始的连续子串；
后缀：必须在最后一个字符结束的连续子串；
真前缀和真后缀：不能等于字符串本身。

ne[i] 表示子串 p[1..i] 的最长相等真前缀与真后缀的长度。用公式表示就是：

ne[i] = \max \left\{k \mid 0 \le k < i,\ p[1..k] = p[i-k+1..i]\right\}.

例如模式串 p = "ababaca"：

$i$	`p[1..i]`	最长相等真前后缀	`ne[i]`
1	`a`	空	0
2	`ab`	空	0
3	`aba`	`a`	1
4	`abab`	`ab`	2
5	`ababa`	`aba`	3
6	`ababac`	空	0
7	`ababaca`	`a`	1

因此，这个模式串的 next 数组为：

下标 i  1 2 3 4 5 6 7
p[i]    a b a b a c a
ne[i]   0 0 1 2 3 0 1

如何求 `next` 数组

遍历模式串时，设 j = ne[i - 1]，表示 p[1..i-1] 当前最长相等真前后缀的长度。要计算 ne[i]，就尝试用新字符 p[i] 继续扩展这个前后缀：

如果 p[i] == p[j + 1]，说明前缀和后缀都能再延长一位，令 j++；
如果两个字符不等，当前长度 j 不可行，就尝试它的次长相等前后缀，令 j = ne[j]；
不断回退，直到成功扩展，或者 j == 0；
把最终的 j 记录到 ne[i]。

// p[1..m] 是模式串
for (int i = 2, j = 0; i <= m; i++) {
  while (j && p[i] != p[j + 1]) {
    j = ne[j];
  }
  if (p[i] == p[j + 1]) {
    j++;
  }
  ne[i] = j;
}

ne[1] 默认为 0，因为长度为 $1$ 的字符串没有非空真前缀和真后缀。

为什么失配后是 `j = ne[j]`

已知 p[1..j] 与当前后缀相等，但 p[j + 1] 无法与新字符匹配。此时如果还存在可行的更短前缀，它必须同时是 p[1..j] 的后缀。ne[j] 恰好记录了这种候选中最长的一个，所以可以直接跳转，而不用从头重新比较。

如何匹配长文本

匹配时，i 指向长文本当前字符，j 表示模式串已经匹配的长度。在比较 s[i] 之前，始终有：

s[i-j..i-1] = p[1..j].

根据 s[i] 和 p[j + 1] 的关系进行转移：

字符相等：当前匹配可以向后扩展，令 j++；
字符不等且 j > 0：令 j = ne[j]，保留已匹配部分的最长可用后缀；
字符不等且 j == 0：当前位置无法作为匹配的开始，继续检查下一个长文本字符。

// s[1..n] 是长文本，p[1..m] 是模式串
for (int i = 1, j = 0; i <= n; i++) {
  while (j && s[i] != p[j + 1]) {
    j = ne[j];
  }
  if (s[i] == p[j + 1]) {
    j++;
  }
  if (j == m) {
    // 匹配成功：按题目要求处理结果
    j = ne[j];
  }
}

例如 s = "abababaca"、p = "ababaca"。当前面已匹配 ababa 、即 j = 5 时，下一个长文本字符是 b，而 p[6] = 'c'，于是失配。

根据 ne[5] = 3，将 j 回退到 3。由于已匹配部分的后缀 aba 也是模式串的前缀，这三个字符无需重新比较；接下来用同一个 s[i] = 'b' 与 p[4] = 'b' 比较即可。

匹配成功后为什么还要回退

当 j == m 时，说明模式串在长文本中出现了一次。记录结果后需要执行：

j = ne[j];

这不仅能避免下一轮访问 p[m + 1]，还能保留完整匹配后的最长可用后缀，从而找到可以重叠的匹配。

例如 s = "aaaaa"、p = "aaa"，模式串的出现位置为 0、1、2。如果匹配成功后把 j 直接清零，就会遗漏后两个重叠匹配。

正确性说明

求 next 数组时，j 始终代表当前已知的最长相等前后缀长度。如果新字符无法扩展它，那么任何更短的可行候选都必须是当前前缀 p[1..j] 的相等前后缀。按照 ne[j]、ne[ne[j]] 依次回退，会从长到短检查所有可能候选，所以最终得到的 ne[i] 是正确的最大长度。

匹配长文本时，如果 s[i] != p[j + 1]，任何可能继续匹配的模式串前缀，都必须等于已匹配文本的某个后缀。ne 链枚举的正是这些候选，因此跳转不会遗漏任何匹配；同时 i 只会向后移动，已经检查过的长文本字符不需要重新扫描。

所以，KMP 可以正确找出模式串在长文本中的所有出现位置。

AcWing 831：KMP 字符串

题意

给定一个模式串 p 和一个长文本 s，求模式串在长文本中所有出现位置的起始下标。题目要求输出 0-based 下标。

在本文的 1-based 字符数组中，当匹配在 s[i] 处结束时：

\text{1-based 起点} = i - m + 1.

转换为题目要求的 0-based 下标后：

\text{0-based 起点} = i - m.

完整代码

#include <iostream>
 
using namespace std;
 
const int N = 100010;
 
char s[N], p[N];
int ne[N];
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int m, n;
  cin >> m >> (p + 1);
  cin >> n >> (s + 1);
 
  // 求模式串 p 的 next 数组
  for (int i = 2, j = 0; i <= m; i++) {
    while (j && p[i] != p[j + 1]) {
      j = ne[j];
    }
    if (p[i] == p[j + 1]) {
      j++;
    }
    ne[i] = j;
  }
 
  // 在长文本 s 中匹配模式串 p
  for (int i = 1, j = 0; i <= n; i++) {
    while (j && s[i] != p[j + 1]) {
      j = ne[j];
    }
    if (s[i] == p[j + 1]) {
      j++;
    }
    if (j == m) {
      cout << i - m << ' ';
      j = ne[j];
    }
  }
 
  cout << '\n';
  return 0;
}

复杂度分析

构造 next 数组时，i 只从左到右遍历模式串，j 的回退总次数不会超过它之前的增长总次数，时间复杂度为 $O(m)$ ；
匹配时，i 不回退，j 也只会沿 next 链回退，时间复杂度为 $O(n)$ ；
算法总时间复杂度为 $O(n + m)$ ；
next 数组占用 $O(m)$ 额外空间。

常见错误

混淆 ne[i] 的含义：本模板中它记录的是最长相等真前后缀的“长度”，不是下一个要跳到的字符下标。
1-based 和 0-based 模板混用：本文使用 p[j + 1] 和 j = ne[j]；0-based 模板常见的写法则是 p[j] 和 j = next[j - 1]，不能拼接使用。
把模式串和长文本长度写反：本文统一令 m 表示模式串长度，n 表示长文本长度。
失配时只回退一次：要用 while 连续回退，直到当前字符能匹配或 j == 0，不能写成 if。
匹配成功后直接清零：应使用 j = ne[j]，否则会遗漏可以重叠的匹配。
输出位置少减一位：当前代码内部是 1-based，但 AcWing 831 要求输出 0-based 起点，所以结果是 i - m。
数组容量不足：使用 p + 1 和 s + 1 读入时，数组需要为末尾的 \0 额外预留空间。

参考资料

AcWing：KMP 模板，作者：yxc（非商业转载请注明出处）。

4-KMP 字符串匹配