📖 第 9.5 章：AC 自动机

🎯 学习目标

学完本章后，你将能够：

1. 理解 fail 指针的定义与作用（KMP 失配思想搬到 Trie 上）
2. 用 BFS 构建 AC 自动机并解释为什么必须按层构建
3. 在文本上运行自动机，完成多模式串的同时匹配与计数
4. 分析总复杂度 O(|T| + Σ|P| + 匹配开销)

9.5.0 问题引入

给定一篇长为 10⁶ 的文章，和 100 个模式串（总长 ≤ 10⁶），请统计每个模式串在文章中出现的次数。

文章：  "she sells seashells by the seashore"
模式串："she", "he", "hers", "sea"
结果：  she → 2 次（位置 0 和 13 内含）
        he  → 4 次（she、shell、the…… 都藏着 he）

（精确数字我们后面用代码验证。）

对每个模式串跑一遍第 9.2 章的 KMP，总复杂度是 O(100 × 10⁶) = 10⁸——勉强能过 1 个模式串 100 次还好，但模式串数目一旦到 10⁴、10⁵ 就彻底不行了。

AC 自动机（Aho-Corasick Automaton，与「自动 AC 机」无关，虽然名字很诱人）把所有模式串一起放进一棵 Trie（第 9.3 章），再给每个节点加一个 fail 指针（失配指针，思想来自第 9.2 章的 KMP），就能在 O(|文本| + Σ|模式串|) 的构建后，一次扫描文本同时匹配所有模式串。

9.5.1 从 Trie 到 AC 自动机

回顾：KMP 失配时怎么办

KMP 匹配单个模式串时，失配不是从头再来，而是跳到 π[j]——当前已匹配部分的最长相等前后缀——继续比较。**「失配后跳到最长后缀对应的位置」**就是这个算法的灵魂。

多模式串的失配：fail 指针

把所有模式串插入 Trie 后，在文本上匹配 = 从根出发，沿文本字符逐个往下走。问题来了：走不下去怎么办？

例如模式串 {"she", "his", "hers"}，文本读到 "shi"——先走 s→h，下一步要匹配 i，但 h 节点下面没有 i 的边（只有 e）。KMP 告诉我们：别回根，找当前已走路径的后缀中，还能在 Trie 里接着走的最长的那条路。"sh" 的后缀 "h" 恰好是 "his" 的前缀，所以应该跳到 "h" 对应的节点，再从那里走 i。

这就是 fail 指针的定义：

fail[u] = Trie 中「u 对应字符串的最长后缀」所在的节点（后缀要严格更短；若不存在这样的后缀，fail[u] = 根）。

三个关键性质：

1. fail 指针总指向更浅的节点（对应更短的字符串），所以沿 fail 链跳有限步必然到根；
2. 一个节点的 fail 链上的所有节点，恰好是它对应字符串的全部「Trie 中存在的前缀后缀」，从长到短排列——文本走到 u 时，以 u 结尾能匹配的模式串，全在 u 及其 fail 链上；
3. 根的所有儿子（长度为 1 的字符串）没有更短的非空后缀，所以它们的 fail 都是根。

一句话总结：fail 指针 = KMP 的 π 数组搬到 Trie 上。 π[i] 是「前缀函数」，fail[u] 是「前缀树上的失配函数」。

模式串 {"she", "his", "hers"} 的 Trie：

        根
       /  \
      s    h
      |    | \
      h    i  e(r s)  ← "hers" 路径
      |    |
      e    s
      ↑
   "she" 的终点 e 节点 u

fail 指针（部分）：
  "she" 的 e 节点 → 后缀 "he"、"e" 在 Trie 中？都不在 → 根
  "hers" 的 s 节点 → 后缀 "s" 在 Trie 中 → s 节点

9.5.2 构建：BFS 层层求 fail

递推关系

fail 指针有一个漂亮的递推结构。设节点 u 的儿子是 ch[u][c]，那么：

求 fail[v]，其中 v = ch[u][c]：从 j = fail[u] 开始，若 ch[j][c] 不存在就一直 j = fail[j] 往上跳；最后 v 的 fail 就是 ch[j][c]（跳到根还不存在则 fail[v] = 根）。

为什么正确？v 对应字符串 = u 对应字符串 + 字符 c。它的最长后缀若非空，去掉末尾的 c 后应该是 u 的某个后缀——而 u 的所有后缀恰好沿 fail[u] 的 fail 链分布，所以从 fail[u] 出发跳链寻找即可。这与 KMP 求 π 时的 j = π[j-1] 跳转一模一样。

为什么必须 BFS？

fail[v] 依赖 fail[u]，而 u 的深度严格小于 v 的深度。按深度从小到大处理，算每个点的 fail 时它依赖的点都算好了——这正是 BFS 的顺序。如果用 DFS，一个深节点的 fail 可能要引用浅节点上还没算出的信息。

实用优化：路径压缩（「图优化」/ trie 图）

构建时顺手做一件事：若 ch[u][c] 不存在，就直接令 ch[u][c] = ch[fail[u]][c]（跳几层后找到的那个转移）。这样构建完成后，自动机上每个节点都有 26 条出边——匹配时再也不需要跳 fail 链找转移，每步 O(1) 走人即可。fail 链只在统计答案时才需要走。

完整构建代码

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

// AC 自动机（数组版，只支持小写字母）
const int MAXN = 1000006;  // 最大节点数 = 所有模式串总长 + 1

int ch[MAXN][26];   // 转移边（构建后为 trie 图，全满）
int fail_[MAXN];   // fail 指针（fail 是关键字，改名 fail_）
int cnt[MAXN];      // cnt[u] = 以节点 u 结尾的模式串个数（可重复）
int tot = 0;        // 节点计数器，根节点为 0

// 插入一个模式串 —— 和普通 Trie 完全一样（第 9.3 章）
void insert_word(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++tot;
            fill(ch[tot], ch[tot] + 26, 0);
            fail_[tot] = 0;
            cnt[tot] = 0;
        }
        p = ch[p][ci];
    }
    cnt[p]++;  // 该节点结尾的模式串数 +1
}

// BFS 构建 fail 指针与 trie 图
void build() {
    queue<int> q;
    // 深度为 1 的节点：fail 指向根
    for (int c = 0; c < 26; c++) {
        if (ch[0][c]) {
            fail_[ch[0][c]] = 0;
            q.push(ch[0][c]);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // 注意：u 的 fail 已在 u 入队前算好
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) {
                // 核心：v 的 fail = u 的 fail 沿链找到的 c 转移
                // 因为 build 时 ch[fail_[u]][c] 已被补全（fail 更浅，先处理过）
                fail_[v] = ch[fail_[u]][c];
                q.push(v);
            } else {
                // 路径压缩：不存在的边指向 fail 链上的转移
                ch[u][c] = ch[fail_[u]][c];
            }
        }
    }
}

int main() {
    // 模式串 {"she", "his", "hers"}
    insert_word("she");
    insert_word("his");
    insert_word("hers");
    build();

    // 验证：打印每个节点的 fail 深度
    // "hers" 的最后一个 s 节点，fail 应指向 "s"（根的儿子）
    cout << "构建完成，共 " << tot << " 个节点" << endl;
    return 0;
}

为什么 fail_[v] = ch[fail_[u]][c] 一句话就够？ 因为 BFS 保证处理 u 时，fail_[u] 已算好，而且更浅的节点都已经过完了路径压缩——ch[fail_[u]][c] 必然存在（最坏是根的转移，指向 0 或根的儿子）。所以不需要 while 循环跳链，一行搞定。这是「边 BFS 边压缩」写法简洁的原因。

9.5.3 匹配：在文本上走自动机

基本流程

把文本 T 逐字符喂给自动机，维护当前节点 p：

p = 0
for c in T:
    p = ch[p][c - 'a']     // trie 图保证转移永远存在，无需跳 fail
    沿 p 的 fail 链统计所有以 p 结尾的模式串

第 9.5.1 节说过：文本走到 p 时，能匹配上的模式串全部在 p 及其 fail 链上。所以统计答案就是沿 fail 链走一遍，累加每个节点的 cnt。

沿 fail 链统计的两种写法

写法 1（直接跳链）：每个位置沿 fail 链走到根，累加 cnt。最坏总代价 O(|T| × 最长模式串)，模式串短时够用，但 "aaaa…" 加上大量 a、aa、aaa… 模式串会把链拉得很长。

写法 2（差分 + fail 树）（推荐）：先只在每个到达的节点 p 上打 +1 标记；扫描完后，按 BFS 逆序把每个节点的标记加到它的 fail 节点上——即fail 树上从叶子到根做一次子树和。这样「每个模式串出现次数」= 它的结尾节点在 fail 树上的子树标记和，整趟匹配严格 O(|T| + Σ|P|)。

完整实战：多模式串出现次数

问题：给定 n 个模式串（总长 ≤ 10⁶）和文本 T（|T| ≤ 10⁶），输出每个模式串在 T 中出现的次数（允许重叠，如 "aa" 在 "aaa" 中出现 2 次）。

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

const int MAXN = 1000006;

int ch[MAXN][26];
int fail_[MAXN];
int cnt[MAXN];      // 该节点结尾的模式串个数
long long hit[MAXN]; // 该节点被文本「路过」的次数（含 fail 树传播）
int tot = 0;
int order_[MAXN];   // BFS 出队顺序（构建时记录，用于逆序传播）
int order_cnt = 0;

void insert_word(const string& s, int& node_id) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++tot;
            fill(ch[tot], ch[tot] + 26, 0);
            fail_[tot] = 0;
            cnt[tot] = 0;
        }
        p = ch[p][ci];
    }
    cnt[p]++;
    node_id = p;  // 记住这个模式串的结尾节点，答案从它读
}

void build() {
    queue<int> q;
    for (int c = 0; c < 26; c++)
        if (ch[0][c]) { fail_[ch[0][c]] = 0; q.push(ch[0][c]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order_[order_cnt++] = u;   // 记录出队顺序
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) {
                fail_[v] = ch[fail_[u]][c];
                q.push(v);
            } else {
                ch[u][c] = ch[fail_[u]][c];
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    // 自测样例（改为读入版只需换掉这两行）
    vector<string> patterns = {"she", "he", "hers", "sea"};
    string text = "she sells seashells by the seashore";

    vector<int> end_node(patterns.size());
    for (size_t i = 0; i < patterns.size(); i++)
        insert_word(patterns[i], end_node[i]);
    build();

    // 匹配：trie 图上每步 O(1) 转移，只在到达节点打标记
    int p = 0;
    memset(hit, 0, sizeof(long long) * (tot + 1));
    for (char c : text) {
        if (c < 'a' || c > 'z') continue;  // 跳过空格等非字母
        p = ch[p][c - 'a'];
        hit[p]++;
    }

    // BFS 逆序传播：把标记沿 fail 边向浅处累加（fail 树自底向上求和）
    for (int i = order_cnt - 1; i >= 0; i--) {
        int u = order_[i];
        hit[fail_[u]] += hit[u];
    }

    // 每个模式串的出现次数 = 其结尾节点的子树标记和
    for (size_t i = 0; i < patterns.size(); i++)
        cout << patterns[i] << " 出现 " << hit[end_node[i]] << " 次\n";
    // 实际输出（可自行验证）：
    // she 出现 2 次（开头的 she，以及 seashells 中的 "sea|she|lls"）
    // he 出现 3 次（she、seashells 中的 she、the 中的 he）
    // hers 出现 0 次
    // sea 出现 2 次（seashells、seashore）
    return 0;
}

验证 "she sells seashells by the seashore"（去掉空格后为 shesellsseashellsbytheseashore）：

• she：开头 "she" ✓ + "seashells" 中 s-e-a-s-h-e-l-l-s 的 "she"（第 4~6 个字符）✓ = 2 次（seashore 中是 sha，不算）；
• he：she 1 次 + seashells 的 she 1 次 + the 的 he 1 次 = 3 次；
• sea：seashells、seashore 各 1 次 = 2 次。

对拍验证：下面把这份代码与「每个模式串独立暴力匹配」做随机对拍。

// 随机生成小写字母文本与模式串，比对 AC 自动机与暴力匹配的统计结果
#include <bits/stdc++.h>
using namespace std;

// ---------- 暴力参照 ----------
int brute_count(const string& T, const string& P) {
    int cnt = 0;
    if (P.size() > T.size()) return 0;
    for (size_t i = 0; i + P.size() <= T.size(); i++)
        if (T.compare(i, P.size(), P) == 0) cnt++;
    return cnt;
}

// ---------- AC 自动机（与正文同款）----------
const int MAXN = 200005;
int ch[MAXN][26], fail_[MAXN], node_cnt_[MAXN], tot2 = 0;
long long hit2[MAXN];
int order2[MAXN], oc2 = 0;

void ins2(const string& s, int& id) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++tot2;
            fill(ch[tot2], ch[tot2] + 26, 0);
        }
        p = ch[p][ci];
    }
    node_cnt_[p]++;
    id = p;
}
void build2() {
    queue<int> q;
    for (int c = 0; c < 26; c++)
        if (ch[0][c]) { fail_[ch[0][c]] = 0; q.push(ch[0][c]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order2[oc2++] = u;
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) { fail_[v] = ch[fail_[u]][c]; q.push(v); }
            else ch[u][c] = ch[fail_[u]][c];
        }
    }
}
vector<long long> ac_count(const vector<string>& ps, const string& T) {
    vector<int> ids(ps.size());
    for (size_t i = 0; i < ps.size(); i++) ins2(ps[i], ids[i]);
    build2();
    memset(hit2, 0, sizeof(long long) * (tot2 + 1));
    int p = 0;
    for (char c : T) { p = ch[p][c - 'a']; hit2[p]++; }
    for (int i = oc2 - 1; i >= 0; i--) hit2[fail_[order2[i]]] += hit2[order2[i]];
    vector<long long> res(ps.size());
    for (size_t i = 0; i < ps.size(); i++) res[i] = hit2[ids[i]];
    return res;
}

int main() {
    srand(12345);
    for (int round = 0; round < 3000; round++) {
        int lenT = 1 + rand() % 60;
        int nP = 1 + rand() % 8;
        int alpha = 2 + rand() % 3;   // 小字母表让匹配更密集
        string T(lenT, 'a');
        for (char& c : T) c = 'a' + rand() % alpha;
        vector<string> ps(nP);
        for (auto& s : ps) {
            int len = 1 + rand() % 6;
            s.resize(len);
            for (char& c : s) c = 'a' + rand() % alpha;
        }
        auto fast = ac_count(ps, T);
        // 重置自动机
        fill(ch[0], ch[0] + 26, 0);
        tot2 = 0; oc2 = 0;
        for (int i = 0; i < nP; i++)
            if (fast[i] != brute_count(T, ps[i])) {
                cout << "MISMATCH at round " << round << "\n";
                return 1;
            }
    }
    cout << "3000 rounds OK\n";
    return 0;
}

9.5.4 应用与复杂度

复杂度分析

若用「写法 1」直接跳 fail 链统计，最坏额外开销是 O(|T| × L)（L 为 fail 链长），遇到恶意构造（如全 a 串 + a, aa, aaa, … 模式串）会退化；差分传播写法没有这个问题。

典型应用

1. 多模式串出现次数（本章实战题）——敏感词过滤、病毒特征扫描的原型；
2. 求文本中出现过哪些模式串：沿 fail 链打布尔标记即可；
3. 配合 DP：「文本中不包含任何模式串的方案数」——把自动机当状态机，在 trie 图上做数位 DP（与第 6.5 章数位 DP的「不包含某子串」技巧同构，但支持多模式串）；
4. fail 树上的子树统计：每个模式串的结尾节点在 fail 树上的子树，恰好是「以它结尾的文本位置集合」——逆序传播就是子树求和。

与前两章的关系

• Trie（第 9.3 章） 提供骨架：插入、节点编号、数组实现全部照搬；
• KMP（第 9.2 章） 提供灵魂：fail 指针 = π 数组的树上版本，BFS 递推 fail_[v] = ch[fail_[u]][c] 与 π[i] = π[π[i-1]]...+1 是同一个套路的两种写法。

⚠️ 常见错误

💪 练习题（本章 3 道，全部含思路与代码）

🟢 基础练习

题目 1：敏感词检测
给定 n 个敏感词（总长 ≤ 10⁵）和一篇文本（长度 ≤ 10⁶），判断文本中是否出现了任何一个敏感词（只需输出 yes/no）。

思路： 建 AC 自动机，文本逐字符转移；每到一个节点沿 fail 链检查是否有 cnt > 0（只需找到任意一个，找到即停）。

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

const int MAXN = 100005;
int ch[MAXN][26], fail_[MAXN], cnt_[MAXN], tot = 0;

void ins(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) { ch[p][ci] = ++tot; fill(ch[tot], ch[tot]+26, 0); }
        p = ch[p][ci];
    }
    cnt_[p] = 1;
}
void build() {
    queue<int> q;
    for (int c = 0; c < 26; c++)
        if (ch[0][c]) { fail_[ch[0][c]] = 0; q.push(ch[0][c]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // 沿 fail 继承标记：fail 链上有词则这里也能匹配到词
        cnt_[u] |= cnt_[fail_[u]];
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) { fail_[v] = ch[fail_[u]][c]; q.push(v); }
            else ch[u][c] = ch[fail_[u]][c];
        }
    }
}
int main() {
    int n; string text;
    cin >> n;
    for (int i = 0; i < n; i++) { string s; cin >> s; ins(s); }
    build();
    cin >> text;
    int p = 0; bool found = false;
    for (char c : text) {
        p = ch[p][c - 'a'];
        if (cnt_[p]) { found = true; break; }
    }
    cout << (found ? "yes" : "no") << "\n";
    return 0;
}

🟡 进阶练习

题目 2：出现次数最多的模式串
给定 n 个模式串和文本 T（长度均 ≤ 10⁶），求出现次数最多的模式串及其次数（出现允许重叠）。

思路： 正是本章 9.5.3 的实战代码——差分标记 + BFS 逆序传播，最后在所有结尾节点中取最大值。

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

const int MAXN = 1000006;
int ch[MAXN][26], fail_[MAXN], tot = 0;
long long hit[MAXN];
int order_[MAXN], oc = 0;

int ins(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) { ch[p][ci] = ++tot; fill(ch[tot], ch[tot]+26, 0); }
        p = ch[p][ci];
    }
    return p;
}
void build() {
    queue<int> q;
    for (int c = 0; c < 26; c++)
        if (ch[0][c]) { fail_[ch[0][c]] = 0; q.push(ch[0][c]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order_[oc++] = u;
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) { fail_[v] = ch[fail_[u]][c]; q.push(v); }
            else ch[u][c] = ch[fail_[u]][c];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<string> ps(n);
    vector<int> ids(n);
    for (int i = 0; i < n; i++) { cin >> ps[i]; ids[i] = ins(ps[i]); }
    build();
    string T; cin >> T;
    int p = 0;
    for (char c : T) { p = ch[p][c - 'a']; hit[p]++; }
    for (int i = oc - 1; i >= 0; i--) hit[fail_[order_[i]]] += hit[order_[i]];
    long long best = 0; int best_i = 0;
    for (int i = 0; i < n; i++)
        if (hit[ids[i]] > best) { best = hit[ids[i]]; best_i = i; }
    cout << ps[best_i] << " " << best << "\n";
    return 0;
}

🔴 挑战练习

题目 3：不包含任何模式串的字符串计数
给定 n 个禁忌串（小写字母，总长 ≤ 20）和长度 L（L ≤ 10⁹），求长度为 L、不包含任何禁忌串作为子串的字符串个数，对 10⁹+7 取模。

思路： 把 AC 自动机当状态机：节点 = 「当前后缀与禁忌串前缀的最长匹配」。有 cnt > 0（沿 fail 继承后）的节点是非法状态。在 trie 图上做矩阵快速幂或线性递推：dp[step][v] += dp[step-1][u]（u 沿每条字符边到 v），答案 = 所有合法节点在步数 L 的 dp 值之和。L 很大时用矩阵快速幂 O((Σ|P|)³ log L)。

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

const int MAXN = 105;
const long long MOD = 1e9 + 7;
int ch[MAXN][26], fail_[MAXN], bad[MAXN], tot = 0;

void ins(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) { ch[p][ci] = ++tot; fill(ch[tot], ch[tot]+26, 0); }
        p = ch[p][ci];
    }
    bad[p] = 1;
}
void build() {
    queue<int> q;
    for (int c = 0; c < 26; c++)
        if (ch[0][c]) { fail_[ch[0][c]] = 0; q.push(ch[0][c]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        bad[u] |= bad[fail_[u]];  // fail 链上有禁忌词 → 此状态也非法
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) { fail_[v] = ch[fail_[u]][c]; q.push(v); }
            else ch[u][c] = ch[fail_[u]][c];
        }
    }
}
int n_sz;  // 状态数 = tot + 1
using Mat = vector<vector<long long>>;
Mat mul(const Mat& A, const Mat& B) {
    Mat C(n_sz, vector<long long>(n_sz, 0));
    for (int i = 0; i < n_sz; i++)
        for (int k = 0; k < n_sz; k++) {
            if (!A[i][k]) continue;
            for (int j = 0; j < n_sz; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        }
    return C;
}
int main() {
    int n; long long L;
    cin >> n >> L;
    for (int i = 0; i < n; i++) { string s; cin >> s; ins(s); }
    build();
    n_sz = tot + 1;
    // 转移矩阵：M[u][v] = 字符 u--c-->v 的方案数（v 非法则不计）
    Mat M(n_sz, vector<long long>(n_sz, 0));
    for (int u = 0; u < n_sz; u++) {
        if (bad[u]) continue;
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (!bad[v]) M[u][v]++;
        }
    }
    // 矩阵快速幂：答案 = e0 * M^L * 全1
    Mat R(n_sz, vector<long long>(n_sz, 0));
    for (int i = 0; i < n_sz; i++) R[i][i] = 1;
    Mat B = M;
    long long e = L;
    while (e) {
        if (e & 1) R = mul(R, B);
        B = mul(B, B);
        e >>= 1;
    }
    long long ans = 0;
    for (int v = 0; v < n_sz; v++) ans = (ans + R[0][v]) % MOD;
    cout << ans << "\n";
    return 0;
}

📋 本章总结

• AC 自动机 = Trie（骨架，第 9.3 章）+ fail 指针（灵魂，第 9.2 章 KMP 思想）
• fail[u] 指向「u 对应字符串的最长后缀」所在的 Trie 节点，沿 fail 链恰好枚举所有可匹配后缀
• 构建必须 BFS：fail[v] 依赖更浅的 fail[u]；边建边做路径压缩，得到全满的 trie 图
• 匹配每步 O(1)；统计用「打标记 + BFS 逆序沿 fail 传播」避免跳链退化
• 总复杂度 O(|T| + Σ|P|)，与模式串个数无关

💡 章节联系： AC 自动机是多模式串世界的 KMP——fail 的递推是同一棵思想之树，只是长在了 Trie 上。学完本部分（第 9.2~9.5 章），你就拥有了从单模式匹配到多模式匹配的完整工具链；再往后是后缀数组 / 后缀自动机等更高阶的结构，它们与第 3.7 章的哈希技术一样，是 OI Wiki「字符串」专题的进阶内容。