AC 自动机：高效多模式串匹配的核心原理与实现

核心逻辑与数学原理

AC 自动机（Aho-Corasick Automaton）的本质是将 KMP 算法的失配转移思想，强行拓扑平移到字典树（Trie Tree）上，构建出的一种多模式串确定性有限状态自动机（DFA）。它能在 $O(N + \\sum L_i)$ 时间复杂度内，完成多个模式串在单文本串中的全量多重匹配。

1. $ ext{fail}$ 指针（失配指针）的数学定义

设 Trie 树上某一节点 $u$ 对应的字符串为 $S_u$。该节点的失配指针 $fail[u]$ 指向节点 $v$，当且仅当： $S_v$ 是 $S_u$ 在整个 Trie 树中能够匹配到的最长真后缀。

2. 状态转移的数学规约与 Trie 图优化

在传统的带 $ ext{fail}$ 指针的 Trie 树上，若当前状态 $u$ 缺失字符 $c$ 的转移边，需要沿着 $fail[u]$ 连续向根节点回溯，直到找到拥有字符 $c$ 的边。这种回溯最坏情况会导致单次状态转移退化为 $O(\text{Depth})$。

AC 自动机采用 Trie 图（Trie Graph） 优化，打破这一效率瓶颈： 对于状态 $u$ 及其读入字符 $c$：

• 若转移边存在（$nxt[u][c] \neq 0$）：该子节点的失配指针直接继承当前节点的失配状态：

$$fail[nxt[u][c]] = nxt[fail[u]][c]$$

• 若转移边不存在（$nxt[u][c] == 0$）：强行将当前缺失的虚边重定向指向其失配节点的对应转移：

$$nxt[u][c] = nxt[fail[u]][c]$$

通过这种空间换时间的路径压缩，Trie 树被重构为一个无缝的 DFA。任何状态面对任何字符，均可在 $O(1)$ 时间内完成精确的状态平移，消除了所有的回溯迭代。

状态设计与算法推导

1. 广度优先搜索（BFS）层序递推 $ ext{fail}$

由于最长真后缀的长度必然严格小于当前串的长度，因此 $ ext{fail}$ 指针的计算必须严格遵循长因数自底向上递推原则。利用队列进行广度优先层序遍历是最完美的解法。

1. 第二层节点初始化：将根节点（0号）的所有直接子节点（深度为 1 的节点）强行入队，并将它们的 $fail$ 全部指向 0。
2. 状态递推：取出队头节点 $u$。遍历所有字符集 $c \in [0, \Sigma-1]$：

• 若 $nxt[u][c]$ 存在，令子节点为 $v$。将 $fail[v]$ 指向 $nxt[fail[u]][c]$，随后将 $v$ 入队。
• 若 $nxt[u][c]$ 不存在，执行路径压缩：nxt[u][c] = nxt[fail[u]][c]。

2. 文本串匹配与计数的数学差分

在单文本串 $S$ 上跑 AC 自动机时，指针 $u$ 随文本字符不断在 DFA 上跳跃。每到达一个节点 $u$，不仅代表以 $u$ 结尾的模式串被触发，所有通过 $fail$ 指针能够间接到达的祖先节点所代表的模式串，也全部在此刻被同时触发。因此，我们需要沿着 $fail$ 链向上收割 exist 标记，或者建立 $ ext{fail}$ 树通过拓扑排序进行贡献累加（高级优化）。

C++ 标准源码（NOIP风格）

下面提供一套标准的、采用 Trie 图优化的 AC 自动机模板源码。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_NODES = 500005; // 总字符节点数上限

int nxt[MAX_NODES][26];
int fail[MAX_NODES];
int cnt_match[MAX_NODES]; // 记录以该节点结尾的模式串个数
int cnt = 0;             // 0 号节点严格充当根节点

// 1. 标准多模式串注入 Trie 树
void insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!nxt[u][c]) {
            nxt[u][c] = ++cnt;
        }
        u = nxt[u][c];
    }
    cnt_match[u]++; // 标记该模式串的结尾
}

// 2. 核心：构建 AC 自动机的 Trie 图与 fail 指针
void build_ac() {
    queue<int> q;

    // 特殊处理第二层节点，防止 fail 指针自环死循环
    for (int i = 0; i < 26; ++i) {
        if (nxt[0][i]) {
            fail[nxt[0][i]] = 0;
            q.push(nxt[0][i]);
        }
    }

    // BFS 层序递推
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < 26; ++i) {
            if (nxt[u][i]) {
                fail[nxt[u][i]] = nxt[fail[u]][i]; // 核心转移：继承最长公共真后缀状态
                q.push(nxt[u][i]);
            } else {
                nxt[u][i] = nxt[fail[u]][i]; // 核心优化：将不存在的边压缩指向失配节点的转移，实现 O(1) 跳转
            }
        }
    }
}

// 3. 核心：在单文本串中检索多模式串的触发频次总和
int query(const string& t) {
    int u = 0;
    int total_ans = 0;

    for (char ch : t) {
        int c = ch - 'a';
        u = nxt[u][c]; // 无论该转移是真边还是被压缩的虚边，均可 $O(1)$ 直接平移

        // 沿着 fail 链向上打扫当前位置能顺带匹配的所有模式串
        for (int t_u = u; t_u && cnt_match[t_u] != -1; t_u = fail[t_u]) {
            total_ans += cnt_match[t_u];
            cnt_match[t_u] = -1; // 致命踩坑点：若题目要求“出现多少种”，搜割完必须置 -1 剪枝，杜绝时间退化
        }
    }
    return total_ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (cin >> n) {
        string pattern;
        for (int i = 0; i < n; ++i) {
            cin >> pattern;
            insert(pattern);
        }

        build_ac();

        string text;
        cin >> text;
        cout << query(text) << "\n";
    }
    return 0;
}

NOIP 实战避坑指南

1. 第二层节点错置导致全盘 RE 或死循环

在 build_ac 进行初始化时，绝对不能将根节点 0 本身压入队列中去递推它自己的子节点。若直接将 0 入队，在执行 fail[nxt[0][i]] = nxt[fail[0]][i] 时，由于 fail[0] 默认为 0，会导致第二层节点的 fail 指针计算逻辑出现毁灭性自环（即 fail[v] = v），这会让后面的 query 在跑 fail 链时瞬间陷入死循环或爆栈 RE。

2. 忽略 query 中 fail 链暴跳导致的“伪 $O(N)$”时间退化（TLE）

很多选手认为用 Trie 图优化后 AC 自动机的时间复杂度就是严格 $O(N)$。这是致命的认知错误。Trie 图只保证了在外层遍历文本串时匹配指针 u 的平移是 $O(1)$ 的；但在内层中，for (int t_u = u; t_u; t_u = fail[t_u]) 这段代码依然存在。如果构造极端恶性数据（如模式串为 a, aa, aaa, aaaa，文本串为一长串 a），每一次状态转移，内层循环都需要强行把 fail 链摸到根节点，单次复杂度直接退化到 $O(\text{模式串总长})$，导致整段程序死于 TLE。 破局策略：若题目仅要求统计各串是否出现，必须像源码中一样在扫描后打上 -1 阻断标记进行剪枝。若要求精确统计各个串出现的次数，严禁在 query 里面暴跳 fail 链，应当只在当前节点打上频次增量标记，最后将所有节点抽离出来，按照 fail 指针建立的 fail 树 进行拓扑排序（拓扑序自底向上）一次性前缀和累加贡献。

经典 NOIP/洛谷 真题

1. 洛谷 P3808 【模板】AC 自动机（简单版）

• 题意描述：给定 $N$ 个模式串和一个文本串 $M$，求有多少个不同的模式串在文本串中出现过。
• 问题本质：多模式串集合覆盖检索基准题。
• 核心解题思路：如上文源码所示。将所有的模式串构建成一个 AC 自动机，对文本串进行单次扫描。扫描过程中通过内层循环沿着 fail 指针向上检索所有被引燃的结束标记，并使用 -1 进行记忆化剪枝，防止因重复访问同一路径而导致的效率崩溃。

2. 洛谷 P3796 【模板】AC 自动机（加强版）

• 题意描述：给定 $N$ 个模式串和一个文本串 $M$，求其中出现次数最多的模式串是哪几个，并按输入顺序输出它们以及各自的最大出现次数。
• 问题本质：多状态触发频次的精确非回溯统计。
• 核心解题思路：

1. 由于需要统计具体每一个串的出现次数，我们在 Trie 树的叶子节点上不能单纯做计数，而是记录该节点对应了第几个输入的模式串的编号 id。
2. 在 query 扫描文本串时，每到一个节点 $u$，不要暴跳 fail 链，直接在这个节点本身的计数器上执行 ans[u]++。
3. 扫描完毕后，我们已知所有的 $fail$ 指针构成了一棵结构严密的树形拓扑（根节点为 0）。按照节点的深度从大到小（即 BFS 队列的逆序，等价于拓扑排序），将子节点的 ans 值打包累加到它的 fail 父亲节点上：ans[fail[u]] += ans[u]。
4. 最后根据模式串编号映射，找出最大值并按要求输出，完美规避了时间退化陷阱。