AC 自动机：Trie 与 fail 指针的多模式匹配

重新整理“AC 自动机：Trie 与 fail 指针的多模式匹配”时，我先翻了自己以前的错误记录，其中最典型的一条就是：我第一次看 AC 自动机时被 fail 指针绕晕了，后来把它看成 Trie 上批量复用失败后的匹配位置，结构才连起来。沿着这个问题再看原理和代码，比直接背结论清楚得多。

AC 自动机用于多模式串匹配。简单说，就是给一堆关键词建一棵 Trie，再加上 fail 指针，让文本扫描时可以在多个关键词之间高效跳转。

它从哪里来

Alfred Aho 与 Margaret Corasick 在 1975 年发表 AC 自动机。它把 Trie 的共享前缀与类似 KMP 的失配跳转结合，使多个模式串能够在一次文本扫描中同时匹配。

为什么不能一个个 KMP

假设有 10 万个敏感词，要在一篇文章里检测命中。如果每个敏感词都跑一次 KMP，文本会被重复扫描很多遍。AC 自动机的思路是：把所有模式串合并到同一棵 Trie 上，文本只扫一遍。

AC 自动机结构

AC 自动机 fail 指针

图：fail 指针表示当前路径失配后，能复用的最长后缀状态

AC 自动机由三部分组成：

Trie 边：表示模式串字符路径。
fail 指针：失配时跳到最长可复用后缀。
输出标记：表示当前节点或 fail 链上是否命中某个模式串。

建 Trie

class Node {
    Node[] next = new Node[26];
    Node fail;
    List<String> outputs = new ArrayList<>();
}

void insert(Node root, String word) {
    Node cur = root;
    for (char ch : word.toCharArray()) {
        int idx = ch - 'a';
        if (cur.next[idx] == null) cur.next[idx] = new Node();
        cur = cur.next[idx];
    }
    cur.outputs.add(word);
}

Trie 负责共享多个模式串的公共前缀。

建 fail 指针

fail 指针通常用 BFS 建。

void buildFail(Node root) {
    Queue<Node> queue = new ArrayDeque<>();
    root.fail = root;
    for (int i = 0; i < 26; i++) {
        if (root.next[i] != null) {
            root.next[i].fail = root;
            queue.offer(root.next[i]);
        } else {
            root.next[i] = root;
        }
    }

    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (int i = 0; i < 26; i++) {
            if (cur.next[i] != null) {
                cur.next[i].fail = cur.fail.next[i];
                cur.next[i].outputs.addAll(cur.next[i].fail.outputs);
                queue.offer(cur.next[i]);
            } else {
                cur.next[i] = cur.fail.next[i];
            }
        }
    }
}

这段写法把缺失转移补齐，匹配时就不用 while 回退，代码更简洁。

匹配文本

List<String> search(Node root, String text) {
    List<String> hits = new ArrayList<>();
    Node cur = root;
    for (char ch : text.toCharArray()) {
        if (ch < 'a' || ch > 'z') {
            cur = root;
            continue;
        }
        cur = cur.next[ch - 'a'];
        hits.addAll(cur.outputs);
    }
    return hits;
}

如果要返回命中位置，遍历时记录下标即可。

工程注意点

真实敏感词系统还要考虑：

中文分词和 Unicode 字符集，不能只用 26 个小写字母数组。
关键词动态更新，自动机构建成本较高。
大词库内存占用，需要压缩节点或使用稀疏 Map。
命中策略：最长匹配、全部匹配、跳过重叠、大小写归一。
误杀问题：词边界和上下文规则比纯算法更复杂。

我的分析

AC 自动机的价值是把多个模式串的匹配合并成一次文本扫描。它不是 KMP 的简单替代品，而是“多模式匹配”的专门工具。工程里如果关键词很少，用 Trie 或普通包含判断可能就够；如果词库大、文本多，AC 自动机才开始体现优势。

面试题

AC 自动机相比多个 KMP 有什么优势？
fail 指针表示什么含义？
为什么 fail 指针通常用 BFS 构建？
中文敏感词系统中，AC 自动机会遇到哪些工程问题？
如果关键词经常动态变化，AC 自动机有什么代价？