AC 自动机 (Aho-Corasick Automaton) 模板详解

靖2025-01-072025-01-07

AC 自动机 (Aho-Corasick Automaton) 模板详解

1. 简介

AC 自动机是一种高效的多模式匹配算法，它结合了 Trie 树和 KMP 算法的思想，可以同时匹配多个模式串。

主要特点：

支持多模式串同时匹配
线性的匹配时间复杂度
可以处理带权值的模式串
支持动态内存管理

2. 实现原理

2.1 基本概念

Trie 树：
- 用于存储所有模式串
- 每个节点代表一个前缀
失配指针：
- 类似 KMP 的 next 数组
- 指向最长的可匹配后缀

2.2 核心策略

构建过程：
- 先构建 Trie 树
- 通过 BFS 建立失配指针
- 累加父节点的权值
匹配过程：
- 沿着 Trie 树移动
- 失配时跳转到失配指针

3. 模板代码

constexpr int N = 3e5 + 30, A = 26;

struct Node {
    int fail;
    int sum;
    int next[A];
    Node() : fail(-1), sum(0) {
        std::memset(next, -1, sizeof(next));
    }
} node[N];

int cnt = 0;
int bin[N];
int nBin = 0;

int newNode() {
    int p = nBin > 0 ? bin[--nBin] : cnt++;
    node[p] = Node();
    return p;
}

struct AC {
    std::vector<int> x;
    AC(AC &&a) : x(std::move(a.x)) {}
    AC(std::vector<std::string> s, std::vector<int> w) {
        x = {newNode(), newNode()};
        std::fill(node[x[0]].next, node[x[0]].next + A, x[1]);
        node[x[1]].fail = x[0];
        
        for (int i = 0; i < int(s.size()); i++) {
            int p = x[1];
            for (int j = 0; j < int(s[i].length()); j++) {
                int c = s[i][j] - 'a';
                if (node[p].next[c] == -1) {
                    int u = newNode();
                    x.push_back(u);
                    node[p].next[c] = u;
                }
                p = node[p].next[c];
            }
            node[p].sum += w[i];
        }
        
        std::queue<int> que;
        que.push(x[1]);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            node[u].sum += node[node[u].fail].sum;
            for (int c = 0; c < A; c++) {
                if (node[u].next[c] == -1) {
                    node[u].next[c] = node[node[u].fail].next[c];
                } else {
                    node[node[u].next[c]].fail = node[node[u].fail].next[c];
                    que.push(node[u].next[c]);
                }
            }
        }
    }
    ~AC() {
        for (auto p : x) {
            bin[nBin++] = p;
        }
    }
    i64 query(const std::string &s) const {
        i64 ans = 0;
        int p = x[1];
        for (int i = 0; i < int(s.length()); i++)  {
            int c = s[i] - 'a';
            p = node[p].next[c];
            ans += node[p].sum;
        }
        return ans;
    }
};

4. 函数说明

4.1 结构体说明

struct Node {
    int fail;    // 失配指针
    int sum;     // 权值和
    int next[A]; // 子节点数组
};

4.2 主要函数

newNode(): 创建新节点
AC(): 构造函数，建立 AC 自动机
query(): 查询字符串的匹配结果

5. 时间复杂度分析

构建时间：O(Σ|Si|)，Si 为模式串长度
查询时间：O(|T|)，T 为待查询串长度
空间复杂度：O(Σ|Si|)

6. 应用场景

多模式串匹配
敏感词过滤
病毒特征码匹配
生物序列匹配

7. 使用示例

7.1 基本使用

vector<string> patterns = {"he", "she", "his", "hers"};
vector<int> weights = {1, 2, 3, 4};
AC ac(patterns, weights);
i64 result = ac.query("hersheis");

7.2 敏感词过滤

vector<string> keywords = {"bad", "worse", "worst"};
vector<int> w(keywords.size(), 1);
AC filter(keywords, w);
string text = "thisisabadword";
if (filter.query(text) > 0) {
    cout << "Contains sensitive words";
}