高效多模式匹配利器（C++语言AC自动机优化详解）

基础实现：构建Trie树

首先，我们需要构建一个Trie树来存储所有待匹配的模式串。

struct Node {    int cnt = 0;               // 以该节点结尾的模式串数量    int fail = 0;              // 失败指针    int next[26] = {0};        // 子节点（假设只处理小写字母）};vector<Node> trie(1);  // 初始根节点void insert(const string& s) {    int u = 0;    for (char c : s) {        int idx = c - 'a';        if (!trie[u].next[idx]) {            trie[u].next[idx] = trie.size();            trie.push_back(Node());        }        u = trie[u].next[idx];    }    trie[u].cnt++;  // 标记此处有一个完整模式串}

构建失败指针（BFS）

失败指针的作用是：当当前字符匹配失败时，跳转到最长公共后缀对应的节点继续匹配。这一步通常用BFS实现。

void build() {    queue<int> q;    // 初始化：根的子节点失败指针指向根    for (int i = 0; i < 26; ++i) {        if (trie[0].next[i]) {            q.push(trie[0].next[i]);        }    }    while (!q.empty()) {        int u = q.front(); q.pop();        for (int i = 0; i < 26; ++i) {            int &v = trie[u].next[i];            if (v) {                trie[v].fail = trie[trie[u].fail].next[i];                q.push(v);            } else {                v = trie[trie[u].fail].next[i];  // 路径压缩优化            }        }    }}

注意上面代码中的 v = trie[trie[u].fail].next[i]; 是一种常见的AC自动机优化技巧，称为“路径压缩”或“转移表预计算”，可以避免在查询时反复跳 fail 指针。

匹配过程

有了构建好的AC自动机，我们就可以高效地在文本中查找所有模式串了。

int query(const string& text) {    int u = 0, res = 0;    for (char c : text) {        u = trie[u].next[c - 'a'];  // 直接跳转（已预计算）        for (int j = u; j; j = trie[j].fail) {            res += trie[j].cnt;            trie[j].cnt = 0;  // 避免重复计数（可选）        }    }    return res;}

高级优化技巧

1. 路径压缩（转移表优化）

如前所述，在构建失败指针时直接更新 next[i]，使得查询时无需循环跳 fail 指针，时间复杂度稳定为 O(n)，其中 n 是文本长度。

2. 内存池与静态数组

使用 vector 动态扩容虽方便，但在高频调用场景下可能影响性能。可改用静态数组或内存池预先分配空间。

3. 输出优化：避免重复遍历 fail 链

若只需判断是否存在匹配（而非统计次数），可在构建时将 cnt 合并到当前节点：

// 在 build() 的 BFS 中加入：trie[u].cnt += trie[trie[u].fail].cnt;

这样查询时只需检查当前节点的 cnt 即可，无需遍历 fail 链。

完整示例

#include <iostream>#include <vector>#include <queue>#include <string>using namespace std;struct Node {    int cnt = 0;    int fail = 0;    int next[26] = {0};};vector<Node> trie(1);void insert(const string& s) {    int u = 0;    for (char c : s) {        int idx = c - 'a';        if (!trie[u].next[idx]) {            trie[u].next[idx] = trie.size();            trie.push_back(Node());        }        u = trie[u].next[idx];    }    trie[u].cnt++;}void build() {    queue<int> q;    for (int i = 0; i < 26; ++i)        if (trie[0].next[i])            q.push(trie[0].next[i]);    while (!q.empty()) {        int u = q.front(); q.pop();        for (int i = 0; i < 26; ++i) {            int &v = trie[u].next[i];            if (v) {                trie[v].fail = trie[trie[u].fail].next[i];                q.push(v);            } else {                v = trie[trie[u].fail].next[i];            }        }        // 可选：合并输出        trie[u].cnt += trie[trie[u].fail].cnt;    }}bool match(const string& text) {    int u = 0;    for (char c : text) {        u = trie[u].next[c - 'a'];        if (trie[u].cnt) return true; // 找到匹配    }    return false;}int main() {    insert("he");    insert("she");    insert("his");    insert("hers");    build();    cout << (match("ahishers") ? "Match found!" : "No match.") << endl;    return 0;}

总结

通过本文，你已经掌握了C++语言AC自动机的基本原理、实现方法以及关键优化技巧。无论是用于竞赛还是工程开发，AC自动机都是处理多模式匹配算法问题的强大工具。记住，核心优化点在于：路径压缩和输出合并，它们能显著提升运行效率。

现在，你可以尝试将其应用到实际项目中，比如实现一个简单的敏感词过滤系统！