AC 自动机 (Aho-Corasick Automaton)¶

AC 自动机（Aho-Corasick Automaton） 是一种用于解决多模式串精确匹配的高效字符串算法。

如果说 KMP 算法 是在单模式串上利用前缀函数实现 $\mathcal{O}(|T| + |P|)$ 的单模匹配，那么 AC 自动机则是 Trie 树（字典树）与 KMP 思想的完美结合，能够在 $\mathcal{O}(\sum |P_i| + |T|)$ 的线性时间内，在主串 $T$ 中同时寻找成千上万个模式串 $P_1, P_2, \dots, P_k$ 的所有出现位置。

1. 核心架构与设计思想¶

AC 自动机由以下三个核心要素构成：

flowchart TD
    A["多模式串集合 P_1, P_2, ..."] --> B["1. 构建基础 Trie 树<br>(公共前缀树)"]
    B --> C["2. BFS 层次遍历构建 Fail 指针<br>(最长公共前后缀跳转)"]
    C --> D["3. 路径压缩为 Trie 图 (字典图)<br>(O(1) 确定性有限状态自动机 DFA)"]

1.1 失配指针 (Fail 指针) 的数学意义¶

对于 Trie 树上的任意节点 $u$，设其从根节点到 $u$ 构成的字符串为 $S(u)$： * $fail[u]$ 指向 Trie 树上的另一个节点 $v$，使得 $S(v)$ 是 $S(u)$ 的最长严格真后缀（Longest Proper Suffix），且 $S(v)$ 必须同时是 Trie 树中的一个合法前缀； * 若不存在这样的后缀，则 $fail[u]$ 指向根节点 $root$。

1.2 BFS 层次遍历构建 Fail 指针与 Trie 图¶

与 KMP 类似，较长前缀的 Fail 指针可以由较短前缀递推得到。因此必须采用 广度优先搜索 (BFS) 按深度逐层构建：

深度为 1 的节点（根节点的直系子节点）：其最长真后缀只能是空串，因此它们的 $fail$ 全部直接指向根节点 $0$；
深度 $\ge 2$ 的节点 $u$：
设当前节点为 $u$，其父节点为 $p$，转移字符为 $c$（即 $p \xrightarrow{c} u$）；
若 $p$ 的某个子节点在字符 $c$ 上不存在，我们直接将其出边补全指向 $fail[p]$ 的对应转移： $$child[p][c] = child[fail[p]][c]$$ 这一优化被称为字典图（Trie Graph），它使得每次字符转移无需循环回跳，永远保持严格 $\mathcal{O}(1)$！
若真实子节点存在，则其 Fail 指针直接等于： $$fail[child[p][c]] = child[fail[p]][c]$$

2. AC 自动机工业级标准模板¶

#include <vector>
#include <string>
#include <queue>
#include <array>

class AhoCorasick {
public:
    static constexpr int ALPHABET_SIZE = 26;

    struct Node {
        std::array<int, ALPHABET_SIZE> next{};
        int fail = 0;
        int count = 0; // 记录以此节点结尾的模式串数量或最长长度
        Node() { next.fill(0); }
    };

    std::vector<Node> tree;

    AhoCorasick() {
        tree.emplace_back(); // 0 号为根节点
    }

    // 插入模式串
    void insert(const std::string& word) {
        int u = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (!tree[u].next[c]) {
                tree[u].next[c] = tree.size();
                tree.emplace_back();
            }
            u = tree[u].next[c];
        }
        tree[u].count++;
    }

    // 构建 Fail 指针与字典图
    void build() {
        std::queue<int> q;
        for (int c = 0; c < ALPHABET_SIZE; ++c) {
            if (tree[0].next[c]) {
                q.push(tree[0].next[c]);
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int c = 0; c < ALPHABET_SIZE; ++c) {
                if (tree[u].next[c]) {
                    // 子节点存在: 其 fail 指向当前节点 fail 的同名子节点
                    tree[tree[u].next[c]].fail = tree[tree[u].fail].next[c];
                    q.push(tree[u].next[c]);
                } else {
                    // 子节点不存在: 字典图补全，直接连向失配后应去往的节点
                    tree[u].next[c] = tree[tree[u].fail].next[c];
                }
            }
        }
    }

    // 在文本串中查询匹配的模式串总次数
    int query(const std::string& text) {
        int u = 0;
        int total_matches = 0;

        for (char ch : text) {
            int c = ch - 'a';
            u = tree[u].next[c]; // 严格 O(1) 转移

            // 沿着 fail 链统计所有以当前字符结尾的模式串
            for (int temp = u; temp && tree[temp].count != -1; temp = tree[temp].fail) {
                total_matches += tree[temp].count;
                // 若每个模式串只统计一次，可标记 tree[temp].count = -1 防止重复遍历
            }
        }
        return total_matches;
    }
};

3. LeetCode 经典真题精选与深度精析¶

LeetCode 1032 - 字符流 (Stream of Characters) 困难
提示

字符流在线匹配：反向 Trie 或正向 AC 自动机。
- 解法一（AC 自动机正向在线转移）：
- 将 words 全部插入 AC 自动机并构建字典图；
- 维护当前自动机的全局指针状态 curr；每次调用 query(letter) 时，执行 curr = tree[curr].next[c]；
- 判断当前状态沿 Fail 链是否存在任何匹配成功的模式串。
- 解法二（倒序后缀 Trie 树）：
- 鉴于查询只关心当前字符结尾的后缀，可将所有模式串逆序插入 Trie 树；
- 维护历史字符流缓存，每次倒序在 Trie 树上匹配，遇终点即返回 true。
- 时间复杂度：每次查询 $\mathcal{O}(1) \sim \mathcal{O}(\text{MaxWordLen})$。
LeetCode 2781 - 最长合法子字符串的长度 (Length of the Longest Valid Substring) 困难
提示

双指针滑动窗口 + 模式串禁止词匹配。
- 题目要求子串内部不能包含 forbidden 中的任何一个词。
- 关键性质：forbidden[i].length <= 10（极短）。
- 维护滑动窗口右端点 $R$：向前最多回看 10 个字符，若发现以 $R$ 结尾的某个后缀在禁止集中，则左端点 $L$ 必须强行右移跨过该非法子串的起点。
- 若模式串长度不设限，则必须使用 AC 自动机在文本串上在线标记所有禁止词的最右结尾位置！
LeetCode 1408 - 数组中的字符串匹配 (String Matching in an Array) 简单
提示

多模式串包含判定。
- 规模极小可以直接双重循环 KMP 或暴力匹配。
- 规模较大时的工业解法是将所有字符串插入 AC 自动机，对每个字符串在自动机上走一次查询是否被其他长串包含。