AC自动机详解，原理、优化分析，代码实现

零、前言

对于模式串匹配问题，在很多基础的数据结构课程中都有涉及到，如 KMP 算法，BM算法，Trie。

但是给定文本串，我们有多个模式串要去查询。难道要多次调用KMP / BM，或者在Trie上多次查询吗？

Aho 和 Corasick 基于 Trie，对 KMP 进行了推广，使得 Trie 可以在一个文本串中识别一个关键字集合中的任何关键字。

这就是本博客的主题——AC自动机。

一、AC 自动机

1.1 概述

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。

AC 自动机本质上是 Trie 上的自动机。

关于KMP：[KMP算法详解 c++]_kmpc+±CSDN博客

关于Trie：[Trie树/字典树的原理及实现C/C++]_trie字典树原理-CSDN博客

1.2 基本原理

建立 AC 自动机一般分为两步：

用所有的模式串构建一个 Trie
为 Trie 上的所有结点构建失配指针(fail)

1.3 Trie 构建

按照普通 Trie 插入模式串的方式将模式串集合中的串依次插入到Trie中

我们在Trie 上匹配模式串的过程，实质上就是在自动机上进行状态转换的过程。

因此，我们可以把Trie 的每个节点看作一个状态，每个状态事实上都对应了某个模式串的前缀。

所以下文有时会称Trie 上的节点为 前缀、状态，这里约定下。

1.4 失配指针

AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

fail 指针：节点（状态） u 的 fail 指针指向另一个节点 v，v 是 u 的最长后缀

换句话说，v 所代表的前缀是 u所代表的前缀的最长后缀

fail vs KMP的next

共同点：两者都是在失配时用于跳转的指针
不同点：next 指针求的是最长公共前后缀，fail 指针则指向的是所有模式串前缀中和当前前缀公共后缀最长的那个

KMP 只对一个模式串做匹配，而AC自动机要对多个模式串做匹配。因而fail 指针可能指向的是另一个模式串，二者前缀不同。

简而言之：AC 自动机的失配指针指向当前状态的最长后缀状态。

下面先解释如何构建fail指针，再解释为何能够通过fail指针来实现多模式串匹配。

1.5 fail 指针的构建

fail 指针的构建其实就是利用 bfs 自顶向下递推的过程，从而避免了后效性。

为了方便描述，先给出节点定义：

struct AhoCorasick {static constexpr int ALPHABET = 26;static constexpr char base = 'a';struct Node {int len;    // 当前前缀长度int fail;   // 失配指针int cnt;    // 此状态结尾单词数目std::array<int, ALPHABET> son;  // 儿子节点Node(): len(0), fail(0), cnt(0), son{} {}};std::vector<Node> tr;	// 节点池
};

构建流程：

队列 q 保存 bfs 过程中的节点
节点 u 从队头出队，此时 u 以及 u 以上的节点的fail 都已经构建完毕
遍历 u 的儿子节点 son[i]
如果 son[i] 为空，那么 son[i] 指向 fail 的 son[i]
如果 son[i] 存在，那么 son[i] 的 fail 指向 u 的 fail 的 son[i]，并将 son[i] 入队
队空，算法结束

由于自顶向下构建，保证了每一个节点出队时，它前面的节点都已构建完毕，保证了对子节点 fail指针构建的正确性。

事实上这是对于暴力构建fail指针的递推优化。

代码如下：

void build_fail() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i])tr[u].son[i] = tr[tr[u].fail].son[i];else {tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];q.push(tr[u].son[i]);}}}
}

放个图可以手玩一下。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

1.6 多模式串匹配

先给出多模式串匹配的代码：

/*文本串: s模式串构建的 AC 自动机: ac
*/
int cur = 1; // 根结点编号为1
int res = 0;
for (char ch : s) {cur = ac.son(cur, ch - 'a');	// 往下跳一步// 开始跳fail，遍历所有后缀for (int newcur = cur; newcur && ac.cnt(newcur) >= 0; newcur = ac.fail(newcur)) {res += ac.cnt(newcur), ac.cnt(newcur) = -1;}
}

默认从根节点开始匹配s
当前节点号为cur
遍历到字符ch
cur = son[ch]
- son[ch] 要么是成功匹配节点，要么是构建fail 时指向的最长后缀的 son[ch]
然后从 cur 开始跳fail，将所有后缀节点都跑一遍，记录匹配

事实上，大部分编译原理课程中都会介绍最长匹配原则，保证了我们的匹配不漏，这点可以自行了解。

1.7 后缀链接优化

尝试自己模拟下这组样例：

target 为文本串，words 为模式串集合

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

发现复杂度会爆炸的

巧妙的是，KMP算法中也对nxt 数组进行了优化，我们这里也是利用类似思想来进行优化。

这里引入后缀链接(link)：

后缀链接（suffix link），用来快速跳到一定是某个模式串的最后一个字母的节点（等于 root 则表示没有）

这样一来节点定义如下：

struct Node {std::vector<int> id;int len;int fail;int last;std::array<int, ALPHABET> son;Node() : last(0), id{}, len(0), fail(0), son{} {}
};

构建过程：

last 是和 fail 在一起构建的：

根节点的 last 默认指向根节点

继承前面bfs 构建fail 的逻辑
u出队，此时u 以及前面的 fail 和 last 都已经构建完毕
遍历 u 的儿子节点 son[i]
如果 son[i] 为空，那么 son[i] 指向 fail 的 son[i]
如果 son[i] 存在，那么 son[i] 的 fail 指向 u 的 fail 的 son[i]
- 如果 son[i].fail 是单词结尾，那么 son[i].last = son[i].fail，否则指向 son[i].fail.last
- 将 son[i] 入队
队空，算法结束

代码如下：

void build() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i]) {tr[u].son[i] = tr[tr[u].fail].son[i];continue;}tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;q.push(tr[u].son[i]);}}
}

1.8 拓扑优化

见OJ练习2.3

1.9 dfs 优化

见OJ练习2.3

二、OJ 练习

2.1 P3808 AC 自动机（简单版I）

原题链接

P3808 AC 自动机（简单版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

如果暴力跳 fail 或者 last 都会TLE，我们对于走过的点打个标记，即 cnt = -1

AC代码

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;struct AhoCorasick {static constexpr int ALPHABET = 26;static constexpr char base = 'a';struct Node {int len;    // 当前前缀长度int fail;   // 失配指针int cnt;    // 此状态结尾单词数目int last;   // 后缀链接std::array<int, ALPHABET> son;  // 儿子节点Node(): last{0}, len(0), fail(0), cnt(0), son{} {}};std::vector<Node> tr;AhoCorasick() {init();}void init() {tr.assign(2, Node());tr[0].son.fill(1);tr[0].len = -1;tr[0].last = 1;}int newNode() {tr.emplace_back();return (int)tr.size() - 1;}int add(const std::string &s) {int cur = 1;for (char ch : s) {int x = ch - base;if (!tr[cur].son[x]) {tr[cur].son[x] = newNode();tr[tr[cur].son[x]].len = tr[cur].len + 1;}cur = tr[cur].son[x];}++ tr[cur].cnt;return cur;}void work() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i]) {tr[u].son[i] = tr[tr[u].fail].son[i];continue;}tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;q.push(tr[u].son[i]);}}}int son(int cur, int x) const{return tr[cur].son[x];}int fail(int cur) const{return tr[cur].fail;}int len(int cur) const{return tr[cur].len;}int size() const{return tr.size();}int last(int cur) const {return tr[cur].last;}int& cnt(int cur) {return tr[cur].cnt;}
};void solve() {int n;std::cin >> n;AhoCorasick ac;for (int i = 0; i < n; ++ i) {std::string s;std::cin >> s;ac.add(s);}ac.work();std::string t;std::cin >> t;int res = 0;for (int i = 0, cur = 1; i < t.size(); ++ i) {cur = ac.son(cur, t[i] - 'a');for (int ncur = cur; ncur && ac.cnt(ncur) >= 0; ncur = ac.last(ncur)) {res += ac.cnt(ncur);ac.cnt(ncur) = -1;}}std::cout << res << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}

2.2 P3796 AC 自动机（简单版 II）

原题链接

P3796 AC 自动机（简单版 II） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

也是板题，额外存个id就行

AC代码

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;struct AhoCorasick{static constexpr int ALPHABET = 26;static constexpr char base = 'a';struct Node{int len;int cnt;int fail;int last;int id;std::array<int, ALPHABET> son;Node(): len{0}, cnt{0}, fail{0}, last{0}, id{-1}, son{} {}};std::vector<Node> tr;AhoCorasick() {init();}void init() {tr.assign(2, Node());tr[0].son.fill(1);tr[0].len = -1;tr[0].last = 1;}int newNode() {tr.emplace_back();return (int)tr.size() - 1;}int add(const std::string &s, int id) {int cur = 1;for (char ch : s) {int x = ch - base;if (!tr[cur].son[x]) {tr[cur].son[x] = newNode();tr[tr[cur].son[x]].len = tr[cur].len + 1;}cur = tr[cur].son[x];}++ tr[cur].cnt;tr[cur].id = id;return cur;}void work() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i]) {tr[u].son[i] = tr[tr[u].fail].son[i];continue;}tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;q.push(tr[u].son[i]);}}}int cnt(int cur) const{return tr[cur].cnt;}int len(int cur) const{return tr[cur].len;}int fail(int cur) const{return tr[cur].fail;}int son(int cur, int x) const{return tr[cur].son[x];}int last(int cur) const{return tr[cur].last;}int id(int cur) const{return tr[cur].id;}
};void solve() {int n;while (std::cin >> n, n)  {AhoCorasick ac;std::vector<std::string> words(n);for (int i = 0; i < n; ++ i) {std::cin >> words[i];ac.add(words[i], i);}ac.work();std::string t;std::cin >> t;std::vector<int> cnt(n);int cur = 1;for (char ch : t) {int x = ch - 'a';cur = ac.son(cur, x);for (int newcur = cur; newcur > 1; newcur = ac.last(newcur))if (~ac.id(newcur))++ cnt[ac.id(newcur)];}int ma = *std::max_element(cnt.begin(), cnt.end());std::cout << ma << '\n';for (int i = 0; i < n; ++ i)if (cnt[i] == ma)std::cout << words[i] << '\n';}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}

2.3 P5357 【模板】AC 自动机（拓扑&dfs优化）

原题链接

P5357 【模板】AC 自动机 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

用后缀链接优化可以跑到84分，我们这个时候有两个选择：

拓扑优化
dfs 优化

二者其实思想相同，只不过一个实现方式是bfs拓扑排序，一个是dfs（类似树形dp）

我们看这个样例图：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

如果我们把fail 边抽离出来会得到什么？

一棵树

因为一个节点只有一条fail边

那么我们按照fail边建树，有两种方式，一个是不改变原图的fail方向，一个是翻转原图fail方向

两种方式分别对应了拓扑和dfs的做法

那么我们在文本串上匹配，每匹配一个字符，自动机都会跳转到一个状态，我们将该状态贡献+1

那么每个模式串都对应着AC自动机上的一个状态节点

每个模式串在文本串中出现次数就是从该状态节点，沿着fail边反方向所能到达节点的贡献和

因而我们可以：

不改变fail边方向建树，进行拓扑排序，在拓扑排序的时候将贡献往后累加
改变fail边方向建树，进行dfs，树形dp计数

AC代码

拓扑优化：

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;struct AhoCorasick{static constexpr int ALPHABET = 26;static constexpr char base = 'a';struct Node{int len;int cnt;int fail;int last;int in;std::array<int, ALPHABET> son;Node(): len{0}, cnt{0}, fail{0}, last{0}, in{0}, son{} {}};std::vector<Node> tr;AhoCorasick() {init();}void init() {tr.assign(2, Node());tr[0].son.fill(1);tr[0].len = -1;tr[0].last = 1;}int newNode() {tr.emplace_back();return (int)tr.size() - 1;}int add(const std::string &s) {int cur = 1;for (char ch : s) {int x = ch - base;if (!tr[cur].son[x]) {tr[cur].son[x] = newNode();tr[tr[cur].son[x]].len = tr[cur].len + 1;}cur = tr[cur].son[x];}++ tr[cur].cnt;return cur;}void work() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i]) {tr[u].son[i] = tr[tr[u].fail].son[i];continue;}tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];++ tr[tr[tr[u].son[i]].fail].in;tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;q.push(tr[u].son[i]);}}}int cnt(int cur) const{return tr[cur].cnt;}int len(int cur) const{return tr[cur].len;}int fail(int cur) const{return tr[cur].fail;}int son(int cur, int x) const{return tr[cur].son[x];}int last(int cur) const{return tr[cur].last;}int &in(int cur) {return tr[cur].in;}int size() const{return tr.size();}
};void solve() {int n;std::cin >> n;AhoCorasick ac;std::vector<int> end(n);for (int i = 0; i < n; ++ i) {std::string s;std::cin >> s;end[i] = ac.add(s);}ac.work();std::string t;std::cin >> t;std::vector<int> f(ac.size());int cur = 1;for (char ch : t) {cur = ac.son(cur, ch - 'a');++ f[cur];}std::queue<int> q;for (int i = 2; i < ac.size(); ++ i)if (!ac.in(i))q.push(i);while (q.size()) {int u = q.front();q.pop();f[ac.fail(u)] += f[u];if (! -- ac.in(ac.fail(u)))q.push(ac.fail(u));}for (int i = 0; i < n; ++ i)std::cout << f[end[i]] << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}

dfs优化：

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;struct AhoCorasick{static constexpr int ALPHABET = 26;static constexpr char base = 'a';struct Node{int len;int cnt;int fail;int last;std::array<int, ALPHABET> son;Node(): len{0}, cnt{0}, fail{0}, last{0}, son{} {}};std::vector<Node> tr;AhoCorasick() {init();}void init() {tr.assign(2, Node());tr[0].son.fill(1);tr[0].len = -1;tr[0].last = 1;}int newNode() {tr.emplace_back();return (int)tr.size() - 1;}int add(const std::string &s) {int cur = 1;for (char ch : s) {int x = ch - base;if (!tr[cur].son[x]) {tr[cur].son[x] = newNode();tr[tr[cur].son[x]].len = tr[cur].len + 1;}cur = tr[cur].son[x];}++ tr[cur].cnt;return cur;}void work() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i]) {tr[u].son[i] = tr[tr[u].fail].son[i];continue;}tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;q.push(tr[u].son[i]);}}}int cnt(int cur) const{return tr[cur].cnt;}int len(int cur) const{return tr[cur].len;}int fail(int cur) const{return tr[cur].fail;}int son(int cur, int x) const{return tr[cur].son[x];}int last(int cur) const{return tr[cur].last;}int size() const{return tr.size();}
};void solve() {int n;std::cin >> n;AhoCorasick ac;std::vector<int> end(n);for (int i = 0; i < n; ++ i) {std::string s;std::cin >> s;end[i] = ac.add(s);}ac.work();std::string t;std::cin >> t;std::vector<int> f(ac.size());int cur = 1;for (char ch : t) {cur = ac.son(cur, ch - 'a');++ f[cur];}std::vector<std::vector<int>> adj(ac.size());for (int i = 2; i < ac.size(); ++ i)adj[ac.fail(i)].push_back(i);auto dfs = [&](auto &&self, int x) -> void {for (int y : adj[x]) {self(self, y);f[x] += f[y];}};dfs(dfs, 1);for (int i = 0; i < n; ++ i)std::cout << f[end[i]] << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}

2.4 L语言

原题链接

https://www.luogu.com.cn/problem/P2292

思路分析

对于每个字符串t，我们要判断其是否可以由给定的字符串集合构造出来

那么考虑dp

定义 f(i) 为 t 的前 i 个字符是否可以被构造

那么 f(i) = f(i - len(s1)) || f(i - len(s2))…

其中 si 为 t[1, i] 的后缀，且 si 在字符串集合中

对于 si 的获取我们可以跳 last 来快速获取

这个题比较 sb 的是洛谷加数据了，题解很多用的状态压缩，实际上不用

我们加两个剪枝：

记 ma 为最长匹配前缀长度

如果 i - ma > 20，我们就break（因为 s 最长也就20）
如果 f[i] 已经为 true，我们就不跳last

AC代码

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;struct AhoCorasick{static constexpr int ALPHABET = 26;static constexpr char base = 'a';struct Node{int len;int cnt;int fail;int last;std::array<int, ALPHABET> son;Node(): len{0}, cnt{0}, fail{0}, last{0}, son{} {}};std::vector<Node> tr;AhoCorasick() {tr.reserve(10000);init();}void init() {tr.assign(2, Node());tr[0].son.fill(1);tr[0].len = -1;tr[0].last = 1;}int newNode() {tr.emplace_back();return (int)tr.size() - 1;}int add(const std::string &s) {int cur = 1;for (char ch : s) {int x = ch - base;if (!tr[cur].son[x]) {tr[cur].son[x] = newNode();tr[tr[cur].son[x]].len = tr[cur].len + 1;}cur = tr[cur].son[x];}++ tr[cur].cnt;return cur;}void work() {std::queue<int> q;q.push(1);while (q.size()) {int u = q.front();q.pop();for (int i = 0; i < ALPHABET; ++ i) {if (!tr[u].son[i]) {tr[u].son[i] = tr[tr[u].fail].son[i];continue;}tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;q.push(tr[u].son[i]);}}}int cnt(int cur) const{return tr[cur].cnt;}int len(int cur) const{return tr[cur].len;}int fail(int cur) const{return tr[cur].fail;}int son(int cur, int x) const{return tr[cur].son[x];}int last(int cur) const{return tr[cur].last;}int size() const{return tr.size();}
};void solve() {int n, m;std::cin >> n >> m;AhoCorasick ac;for (int i = 0; i < n; ++ i) {std::string s;std::cin >> s;ac.add(s);}ac.work();for (int i = 0; i < m; ++ i) {std::string t;std::cin >> t;n = t.size();std::vector<bool> f(n + 1);f[0] = true;int cur = 1;int ma = 0;for (int i = 1; i <= n; ++ i) {cur = ac.son(cur, t[i - 1] - 'a');for (int newcur = cur; newcur > 1; newcur = ac.last(newcur)) {if (f[i]) break;if (ac.cnt(newcur)) {f[i] = f[i] || f[i - ac.len(newcur)];}}if (f[i]) ma = i;if (i - ma > 20) break;}std::cout << ma << '\n';}}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}