Lesson 0417 · 字符串匹配：KMP

④ 数据结构与算法 — 第 17 课

1. 暴力匹配慢在哪

最直接的做法：让短串 s2 从长串 s1 的每个位置开始，一个字符一个字符比：

for (int i = 0; i + m <= n; i++) {
    int k = 0;
    while (k < m && s1[i + k] == s2[k]) k++;
    if (k == m) 找到一个匹配（位置 i + 1）
}

复杂度是 O(n·m)。最坏情况长这样：

s1 = AAAAAAAA…A     （100 万个 A）
s2 = AAAAA…AAB      （999 个 A 加一个 B）

每次都在最后一个字符上失败，于是每个起点都要白比 1000 个字符。实测（n1 = 106、n2 = 1000）：247 ms；把 n2 加到 8000，直接 1885 ms。

2. 核心概念：border 与 pi 数组

先看一个字符串：ABABCABAA。它的前缀 ABABCABA 有一个性质：

• 开头两位是 AB
• 结尾两位也是 AB（…AB 里的 AB）

「既是前缀、又是后缀」且不是自己的那个最长子串，叫 border。这里 ABABCABA 的最长 border 是 ABA（长度 3）。

手推 ABABCABAA 的 pi

所以 pi = 0 0 1 2 0 1 2 3 1（程序实测输出一致）。

看 i = 8 那一行：它回退了两次（3 → 1 → 0），然后才重新配上。这就是 pi 数组最反直觉的地方 —— 失配时不是从 0 开始，而是沿着 pi 一层层往下退，每一层都还是「可能继续匹配的前缀」。

3. pi 是怎么递推出来的

核心就三行：

for (int i = 1; i < m; i++) {
    int j = pi[i - 1];                              // 从「上一个前缀的最长 border」接着试
    while (j > 0 && s2[i] != s2[j]) j = pi[j - 1];  // 配不上就退一层，退到 0 为止
    if (s2[i] == s2[j]) j++;                        // 配上了，border 长度 +1
    pi[i] = j;
}

4. 匹配：i 只往前走，j 可以往回退

有了 pi 数组，匹配就是同一套循环：

int j = 0;
for (int i = 0; i < n; i++) {
    while (j > 0 && s1[i] != s2[j]) j = pi[j - 1];   // 失配：退 j，不动 i
    if (s1[i] == s2[j]) j++;                          // 配上：j 往前走
    if (j == m) {                                     // 整个模式串配完了
        cout << i - m + 2 << '\n';                    // 出现位置（1-based）
        j = pi[j - 1];                                // ★ 继续找下一处（可能重叠）
    }
}

用样例 s1 = ABABABC、s2 = ABA（pi = 0 0 1）逐字符走一遍：

输出 1、3 —— 和样例一致。

5. 完整代码（P3375 可直接交）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s1, s2;
    cin >> s1 >> s2;
    int n = (int)s1.size(), m = (int)s2.size();

    // ① 求 pi 数组
    vector<int> pi(m, 0);
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];
        while (j > 0 && s2[i] != s2[j]) j = pi[j - 1];
        if (s2[i] == s2[j]) j++;
        pi[i] = j;
    }

    // ② 匹配
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && s1[i] != s2[j]) j = pi[j - 1];
        if (s1[i] == s2[j]) j++;
        if (j == m) {
            cout << i - m + 2 << '\n';   // 1-based 位置
            j = pi[j - 1];
        }
    }

    // ③ 输出 pi 数组（P3375 要求的最后一行）
    for (int i = 0; i < m; i++) cout << pi[i] << (i + 1 == m ? '\n' : ' ');
}

实测四组（本机编译运行，-O2 -std=c++17 -Wall -Wextra 零警告）：

6. 实测：KMP 到底快多少

固定 n1 = 106，模式串是「n2−1 个 A 加一个 B」（最坏情况：每次都在最后一个字符失败）：

KMP 一列几乎不动（1.5–1.9 ms），暴力一列随 n2 线性涨 —— 这就是 O(n+m) 与 O(n·m) 的区别，不是常数快慢。

另外两组真实场景：

正确性也对拍过：500 组随机小串，KMP 的结果与暴力完全一致（0 组不一致）。

7. 坑点清单

• j = pi[j - 1]，不是 pi[j]：差一格，小数据可能蒙对，大数据必挂
• 匹配成功后要 j = pi[j-1]：否则漏掉重叠匹配（AAAAA 找 AA 只报 1 处）
• 位置是 1-based：i - m + 2（因为 i 是 0-based 的末尾下标）
• P3375 最后一行要输出 |s2| 个 pi 值，含 pi[0] = 0；空格隔开、行末换行，别输出成一行位置
• j == m 时不能再用 s2[j]：越界；回退要立刻做
• 两行快读要写：ios::sync_with_stdio(false); cin.tie(nullptr);，字符串 10⁶ 级时差别明显
• pi 用 int 就够（值 ≤ 10⁶），不用 long long
• 单字符模式串（m = 1）：求 pi 的循环一次都不跑，pi[0] = 0，别写成从 0 开始导致越界

8. 小测

9. 动手练习

1. P3375 【模板】KMP —— 主战场。|s1|, |s2| ≤ 106，全大写字母。三件必须自己对的东西：① 位置是 1-based（i - m + 2）；② 最后一行输出 |s2| 个 pi 值、空格隔开；③ 匹配成功后立刻 j = pi[j-1]。
2. 自测重叠：拿 AAAAA 找 AA，答案应该是 4 处（1、2、3、4）。如果你只输出 1 处，就是匹配后没回退。
3. 选做：用 KMP 数出现次数——同一份代码把「输出位置」换成「计数器 +1」，就是「统计子串出现次数」的模板题。

本课小结

• 暴力匹配 O(n·m)，慢在「每次失败都扔掉已比过的信息」
• pi[i] = 前缀 s[0..i] 的最长 border 长度；ABABCABAA → 0 0 1 2 0 1 2 3 1
• 求 pi 三行：j = pi[i-1] → while (j > 0 && s[i] != s[j]) j = pi[j-1] → 配上则 j++
• 匹配：i 只前进，失配只退 j；j == m 时记录位置并 j = pi[j-1]
• 复杂度 O(n+m)：j 回退总次数被「增加次数」卡住
• 实测：n1 = 106 最坏数据上 KMP 1.6 ms vs 暴力 247 ms；n2 从 500 加到 8000，暴力从 126 ms 涨到 1885 ms，KMP 几乎不动
• 最容易错的一行：pi[j-1] 写成 pi[j]