第40讲：AC自动机——多模式串匹配的利器

说实话，我第一次接触AC自动机的时候，心里是有点发怵的。那时候我在做一个敏感词过滤系统，需要同时匹配几千个关键词。用KMP一个个去比？太慢了。用Trie树？只能做前缀匹配，没法处理模式串出现在文本中间的情况。后来一位老同事跟我说：「你试试AC自动机吧。」嗯，这一试，就再也没放下过。

AC自动机是什么？

AC自动机，全称Aho-Corasick自动机。它本质上是一个多模式串匹配算法。你想想看，KMP只能匹配一个模式串，而AC自动机可以同时匹配多个。它把Trie树和KMP的失配思想结合在了一起——说白了，就是在Trie树上加了一套「失败指针」系统。

我个人的理解是：AC自动机 = Trie树 + Fail指针。Trie树负责组织所有模式串，Fail指针负责在匹配失败时快速跳转。

核心思想：在Trie树上构建Fail指针，使得当某个字符匹配失败时，自动机能够沿着Fail指针跳转到另一个分支继续匹配，而不是回到根节点重新开始。

Trie树的构建

我们先从Trie树说起。假设我们有三个模式串：he、she、his。把它们插入到Trie树中，每个节点代表一个字符，根节点为空。

// Trie树节点定义
typedef struct TrieNode {
    struct TrieNode *children[26];  // 假设只有小写字母
    struct TrieNode *fail;          // Fail指针
    int count;                      // 以该节点结尾的模式串数量
} TrieNode;

// 插入模式串
void insert(TrieNode *root, const char *pattern) {
    TrieNode *p = root;
    for (int i = 0; pattern[i] != '\0'; i++) {
        int idx = pattern[i] - 'a';
        if (p->children[idx] == NULL) {
            p->children[idx] = (TrieNode *)calloc(1, sizeof(TrieNode));
        }
        p = p->children[idx];
    }
    p->count++;  // 标记为一个模式串的结尾
}

这段代码看起来很简单对吧？就是标准的Trie树插入。但注意，我这里用calloc而不是malloc，因为calloc会把内存清零，这样所有指针初始就是NULL，省得我们手动初始化。

小技巧：我在项目中习惯把Trie树的根节点单独分配，并且把它的Fail指针指向自己。这样在构建Fail指针时，边界条件处理起来会清爽很多。

Fail指针的构建——核心中的核心

好，Trie树建好了。接下来就是AC自动机的灵魂——Fail指针。它的作用是什么？当你在某个节点匹配失败时，Fail指针告诉你「你应该跳到哪个节点继续匹配」。

构建Fail指针用的是BFS（广度优先搜索）。为什么是BFS？因为子节点的Fail指针依赖于父节点的Fail指针，所以必须按层处理。

// 构建Fail指针（BFS）
void buildFail(TrieNode *root) {
    Queue *q = createQueue();
    
    // 第一层节点：Fail指针指向根节点
    for (int i = 0; i < 26; i++) {
        if (root->children[i] != NULL) {
            root->children[i]->fail = root;
            enqueue(q, root->children[i]);
        }
    }
    
    while (!isEmpty(q)) {
        TrieNode *current = dequeue(q);
        
        for (int i = 0; i < 26; i++) {
            TrieNode *child = current->children[i];
            if (child == NULL) continue;
            
            // 核心：沿着父节点的Fail指针向上找
            TrieNode *f = current->fail;
            while (f != root && f->children[i] == NULL) {
                f = f->fail;
            }
            
            if (f->children[i] != NULL && f->children[i] != child) {
                child->fail = f->children[i];
            } else {
                child->fail = root;
            }
            
            // 合并计数：如果Fail指针指向的节点是模式串结尾，当前节点也算
            child->count += child->fail->count;
            
            enqueue(q, child);
        }
    }
}

这段代码里，我加了一个优化：child->count += child->fail->count。这样在匹配时，只要走到某个节点，就能知道当前路径上包含了多少个模式串。我曾经在一个日志分析项目里用这个优化，把匹配速度提升了将近一倍。

注意：构建Fail指针时，一定要处理好根节点的子节点。如果某个子节点不存在，不要直接跳过，而是要考虑「虚拟节点」的概念。有些实现会为不存在的子节点创建一个指向根节点的指针，这样匹配时就不用每次都while循环了——这叫「Trie图优化」，后面会讲到。

多模式串匹配过程

匹配过程其实很简单：从根节点开始，逐个读入文本字符。如果当前节点有对应的子节点，就走过去；如果没有，就沿着Fail指针跳转，直到找到匹配或者回到根节点。

// 多模式串匹配
void match(TrieNode *root, const char *text) {
    TrieNode *p = root;
    
    for (int i = 0; text[i] != '\0'; i++) {
        int idx = text[i] - 'a';
        
        // 如果当前节点没有这个子节点，沿Fail指针跳转
        while (p != root && p->children[idx] == NULL) {
            p = p->fail;
        }
        
        if (p->children[idx] != NULL) {
            p = p->children[idx];
        }
        
        // 检查当前节点是否匹配到模式串
        if (p->count > 0) {
            printf("在位置 %d 匹配到模式串\n", i);
        }
    }
}

你看，匹配的代码比构建Fail指针简单多了。但这里有个坑：while循环可能会执行很多次。如果文本很长，这个循环会成为性能瓶颈。怎么优化？

优化方案：Trie图——在构建Fail指针时，把不存在的子节点直接指向Fail指针跳转后的节点。这样匹配时就不需要while循环了，直接走p = p->children[idx]就行。代价是内存占用会大一些，但换来的是O(n)的匹配时间复杂度。

AC自动机的应用场景

AC自动机在实际项目中用得非常多。我列几个我亲身经历过的：

  • 敏感词过滤：这是最常见的应用。把敏感词列表建成AC自动机，然后扫描用户输入。我在一个社交平台项目里做过这个，几千个敏感词，扫描一篇千字文章只需要几毫秒。
  • 病毒特征码匹配：杀毒软件需要同时匹配成千上万个病毒特征码。AC自动机是这类场景的标准解法。
  • 基因序列匹配：在生物信息学中，经常需要在一段DNA序列中查找多个已知片段。AC自动机比逐个匹配快得多。
  • 关键词提取：从文本中提取所有预定义的关键词。比如新闻分类、标签推荐等。

AC自动机 vs 其他算法

算法 模式串数量 预处理时间 匹配时间复杂度 适用场景
KMP 1个 O(m) O(n) 单模式串匹配
Trie树 多个 O(∑m) O(n * L) 前缀匹配
AC自动机 多个 O(∑m) O(n) 多模式串匹配
暴力匹配 多个 无 O(n * k * m) 模式串极少时

从表格可以看出，AC自动机在模式串数量多、文本长度大的场景下，优势非常明显。它的匹配时间只与文本长度有关，与模式串数量无关——这才是它最厉害的地方。

SVG流程图：AC自动机核心逻辑

AC自动机核心逻辑 根 h s e i h e Trie树边 Fail指针 模式串结尾节点

这张图展示了一个简单的AC自动机结构。模式串是he、hi、she。红色虚线是Fail指针，你可以看到：当在sh节点匹配失败时，Fail指针指向h节点，而不是回到根节点——这就是AC自动机高效的原因。

避坑指南

我在实际使用AC自动机时，踩过几个坑，分享给你：

  • 内存泄漏：Trie树的节点数量可能很大（几万甚至几十万），每个节点又有一个26个指针的数组。如果不用递归释放，很容易漏掉。我建议写一个destroyTrie函数，用后序遍历释放所有节点。
  • 字符集大小：如果字符集不是26个小写字母，而是ASCII（256个字符）甚至Unicode，那每个节点的children数组就会非常大。这时候可以用哈希表或者动态数组来存储子节点，以空间换时间。
  • 重复模式串：如果模式串列表中有重复的，记得在插入时累加count，而不是覆盖。否则会漏掉匹配。

我的经验：曾经有一个项目，模式串里有中文。我一开始用Unicode码点作为索引，结果内存爆了。后来改用双数组Trie（Double-Array Trie）来压缩存储，才把内存降下来。如果你的字符集很大，可以考虑这个方案。

总结

AC自动机是一个把Trie树和KMP思想巧妙结合的算法。它的核心在于Fail指针的构建——这决定了匹配时的跳转效率。我个人觉得，理解AC自动机最好的方式就是动手实现一遍，然后拿几个模式串和一段文本去调试，看看Fail指针是怎么跳转的。

嗯，这一讲的内容就到这里。AC自动机虽然看起来复杂，但只要你理解了Trie树和Fail指针的关系，剩下的就是代码实现的问题了。多写几遍，自然就熟了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →