AC 自动机 - LeAf146

LeAf146

公告

叶子的博客，随便看看吧。

Learn More

标签

服务器网络字符串 ACM Agnet AI Blog Blogging codeforces

1954 字

8 分钟

AC 自动机

2026-08-02

ACM

Blog

/

ACM

/

字符串

引入#

先推荐一下23级学长warzone 的题解和yyb佬的博客。

我们用 KMP 解决了一个模式串匹配一个主串的问题，那如果有多个模式串该怎么办？

AC 自动机是一种支持多模式串匹配的数据结构。在构造完成后，可以用 $O(|S|+匹配结果数量)$ 的时间求出若干个模式串 $T_{1},T_{2}\dots,T_{n}$ 在 $S$ 中出现了几次，出现在哪里等问题。

相较于 KMP，简直遥遥领先！（除了空间复杂度略大一点）

暴力解法#

先想当然一下，我们之前学习了 KMP，在此基础上，最好的方法，无非就是对每一个模式串都做一遍 KMP，时间复杂度是 $O\left( n|S|+\sum_{1}^{n} |T_{i}| \right)$ 。

对于主串 $S$ ，我们进行了很多重复的查询。有什么优化方法，让我们只查询一次主串就解决问题？

把模式串组合成一个！

AC 自动机#

概述#

结合前面 Trie 的学习，我们很轻松 ~~(并非很轻松)~~ 就能想到使用 Trie 来组合模式串，再在 Trie 上建立失配函数，以实现只查询一次主串就解决问题的目的。

简单来说，建立一个 AC 自动机有两个步骤：

将所有模式串构建成一棵 Trie。
对 Trie 上所有结点构造失配指针。

下面是字符串集合 $\{ab,bca,caa\}$ 构建的 AC 自动机。 AC 自动机示意图

第一步：由字符串集合构建 Trie。具体步骤不再赘述。

第二步：构造失配指针。失配指针的作用和 KMP 中的 fail 数组相同，指向当前字符失配后需要跳转到的结点。含义也类似。原本在一个字符串中，fail[i]=j 的含义是 $P[0,1,\dots,i-1]$ 的最长相等前后缀长度为 $j$ 。由于我个人习惯 0-base，所以这个 $j$ 恰好也是模式串对应位置的下标。而在 Trie 上，fail[u] 指向结点 v 的含义是，从 $root$ 到 $v$ 的结点所表示的字符串，是从 $root$ 到 $u$ 的结点所表示的字符串的最长真后缀。

说起来有些绕，但是画一画图就很好理解了。

求失配指针#

首先，我们可以确定，每一个结点 $u$ 的失配指针指向的点的深度，一定比 $u$ 的深度要小。

也就是说，第二层的结点的失配指针一定指向根节点。

设结点 $u$ 的父亲 $f$ 的失配指针指向 $v_f$ 。那么如果 $v_{f}$ 有和 $u$ 值（这里我们假定结点的值就是指向结点的边的值）相同的子结点 $v$ ，那么 $u$ 的失配指针就指向 $v$ 。如果没有，则继续沿 $v_f$ 的失配指针向前，直到找到一个存在相同子结点的结点。如果跳到根节点仍找不到符合条件的结点，则令 $u$ 的失配指针指向 $root$ 。

这里可能难以理解，还是建议画图。

由于我们在处理失配指针时，需要查看父节点的失配指针，所以我们采用 BFS 来实现。

1
void build() {
2
    for (auto& node : tree) {
3
        node.fail = 0;
4
        node.outputlink = 0;
5
    }
6
    queue<int> q;
7
    for (auto& [c, v] : tree[0].child) {
8
        tree[v].fail = 0;
9
        tree[v].outputlink = 0;
10
        q.push(v);
11
    }
12
    while (q.size()) {
13
        int u = q.front();
14
        q.pop();
15
        for (auto& [c, v] : tree[u].child) {
16
            int p = tree[u].fail;
17
            while (p != 0 && tree[p].child.find(c) == tree[p].child.end())
18
                p = tree[p].fail;
19
            auto pos = tree[p].child.find(c);
20
            if (pos != tree[p].child.end() && pos->second != v)
21
                tree[v].fail = pos->second;
22
            else
23
                tree[v].fail = 0;
24
            int f = tree[v].fail;
25
            if (tree[f].index.size())
26
                tree[v].outputlink = f;
27
            else
28
                tree[v].outputlink = tree[f].outputlink;
29
            q.push(v);
30
        }
31
    }
32
    built = 1;
33
}

整体代码#

这里我为了泛用性，导致代码很长，实际使用中只需要按需编写即可，最重要的还是理解算法。

1
template <typename T> struct AhoCorasick {
2
    struct Node {
3
        unordered_map<T, int> child;
4
        vector<int> index;
5
        int fail = 0, outputlink = 0;
6
    };
7
    vector<Node> tree;
8
    vector<int> length; // 在模式串 id 不连续，或范围很大时，可以使用 unordered_map
9
    bool built = 0;
10
    AhoCorasick() { tree.emplace_back(); }
11

12
    template <typename Iterator> void insert(Iterator begin, Iterator end, int id) {
13
        int u = 0, len = 0;
14
        for (auto it = begin; it != end; it++, len++) {
15
            const T& c = *it;
16
            auto pos = tree[u].child.find(c);
17
            if (pos == tree[u].child.end()) {
18
                int v = tree.size();
19
                tree[u].child[c] = v;
20
                tree.emplace_back();
21
                u = v;
22
            } else
23
                u = pos->second;
24
        }
25
        if (length.size() <= id)
26
            length.resize(id + 1);
27
        length[id] = len;
28
        tree[u].index.push_back(id);
29
        built = 0;
30
    }
31
    void build() {
32
        for (auto& node : tree) {
33
            node.fail = 0;
34
            node.outputlink = 0;
35
        }
36
        queue<int> q;
37
        for (auto& [c, v] : tree[0].child) {
38
            tree[v].fail = 0;
39
            tree[v].outputlink = 0;
40
            q.push(v);
41
        }
42
        while (q.size()) {
43
            int u = q.front();
44
            q.pop();
45
            for (auto& [c, v] : tree[u].child) {
46
                int p = tree[u].fail;
47
                while (p != 0 && tree[p].child.find(c) == tree[p].child.end())
48
                    p = tree[p].fail;
49
                auto pos = tree[p].child.find(c);
50
                if (pos != tree[p].child.end() && pos->second != v)
51
                    tree[v].fail = pos->second;
52
                else
53
                    tree[v].fail = 0;
54
                int f = tree[v].fail;
55
                if (tree[f].index.size())
56
                    tree[v].outputlink = f;
57
                else
58
                    tree[v].outputlink = tree[f].outputlink;
59
                q.push(v);
60
            }
61
        }
62
        built = 1;
63
    }
64
    template <typename Iterator> vector<pair<int, int>> query(Iterator begin, Iterator end) {
65
        if (!built)
66
            build();
67
        vector<pair<int, int>> ans;
68
        int u = 0, pos = 0;
69
        for (auto it = begin; it != end; it++, pos++) {
70
            const T& c = *it;
71
            while (u != 0 && tree[u].child.find(c) == tree[u].child.end())
72
                u = tree[u].fail;
73
            auto poss = tree[u].child.find(c);
74
            if (poss != tree[u].child.end())
75
                u = poss->second;
76
            else
77
                u = 0;
78
            for (int id : tree[u].index)
79
                ans.push_back({ id, pos - length[id] + 1 });
80
            for (int v = tree[u].outputlink; v != 0; v = tree[v].outputlink) {
81
                for (int id : tree[v].index)
82
                    ans.push_back({ id, pos - length[id] + 1 });
83
            }
84
        }
85
        return ans;
86
    }
87
};