什么是 AC 自动机
AC 自动机（Aho-Corasick Automaton）由 Alfred Aho 和 Margaret Corasick 于 1975 年提出，是用于多模式字符串匹配的算法：给定多个模式串，在主串中一次性找出所有模式串的出现位置。它结合了 Trie 树（组织模式串）和 KMP（失败跳转思想），时间复杂度为 O(n + m + z)，其中 n 是主串长度、m 是全部模式串总长度、z 是匹配成功次数。
适用场景：敏感词过滤、病毒特征码扫描、DNA 序列中的多模式查找等。
核心思想：Trie + 失败指针
AC 自动机由三部分组成：
- Trie 树：把所有模式串插入一棵字典树，公共前缀共享路径；
- 失败指针（Fail）：类似 KMP 的 next 数组——当前字符匹配失败时，跳到另一个节点继续匹配，而不是回到根重新开始；
- 输出（Output）：每个节点记录”走到这里能匹配出哪些模式串”。
构建步骤
1. 构建 Trie 树
以模式串集合 ["he", "she", "his", "hers"] 为例，构建的 Trie 如下（* 表示某个模式串的结尾）：
(root)
/ |
h s
/
e i h
/
* s i
* r
s
*
2. 构建失败指针（BFS）
失败指针的构建规则：
- 根节点的失败指针指向空；
- 根节点的直接子节点：失败指针指向根；
- 其他节点：看父节点的失败指针指向的节点是否存在相同字符的子节点——存在则指向它，否则继续沿失败指针向上找，直到根。
用 BFS 逐层构建。例如 h 的失败指针指向根；s（”his” 的 s）的失败指针：父 i 的失败指针 h 有 s 子节点吗？有（”she” 的 s），所以指向它。
3. 输出函数
一个节点能输出的模式串，除了”以它结尾的模式串”，还要加上它失败指针链上所有节点的输出——因为走到这里意味着这些后缀同时也是某个模式串的前缀路径。在 BFS 建失败指针时直接把 fail 节点的输出合并进来即可。
匹配过程
从根出发逐个读主串字符：
- 当前字符匹配：沿子节点前进，收集该节点（含失败链）的所有输出；
- 当前字符不匹配：沿失败指针跳转，直到找到匹配的子节点或回到根。
示例：主串 "ahishers"，模式串 ["he","she","his","hers"]：
'a': 无匹配，停留根
'h': 进入 h 节点
'i': 进入 i 节点，输出 "his"
's': 进入 s 节点，输出 "hers"（检查失败链时发现 "she"）
'h': s 的失败指针跳到 h 的 s 子节点，其失败指针回到 h，继续匹配
'e': 进入 e 节点，输出 "he"
最终匹配结果: "his"、"hers"、"he"
完整代码（C++）
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
TrieNode* fail = nullptr;
vector<int> output; // 在此节点结束的模式串索引
};
class ACAutomaton {
private:
TrieNode* root;
vector<string> patterns;
void buildTrie(const vector<string>& ps) {
patterns = ps;
root = new TrieNode();
for (int i = 0; i < (int)ps.size(); ++i) {
TrieNode* node = root;
for (char c : ps[i]) {
if (!node->children.count(c))
node->children[c] = new TrieNode();
node = node->children[c];
}
node->output.push_back(i);
}
}
void buildFail() {
queue<TrieNode*> q;
for (auto& [c, child] : root->children) {
child->fail = root;
q.push(child);
}
while (!q.empty()) {
TrieNode* cur = q.front(); q.pop();
for (auto& [c, child] : cur->children) {
TrieNode* f = cur->fail;
while (f && !f->children.count(c)) f = f->fail;
child->fail = (f == nullptr) ? root : f->children[c];
// 合并失败节点的输出
child->output.insert(child->output.end(),
child->fail->output.begin(),
child->fail->output.end());
q.push(child);
}
}
}
public:
ACAutomaton(const vector<string>& patterns) {
buildTrie(patterns);
buildFail();
}
vector<int> search(const string& text) {
vector<int> matches;
TrieNode* node = root;
for (char c : text) {
while (node && !node->children.count(c)) node = node->fail;
if (!node) { node = root; continue; }
node = node->children[c];
for (int idx : node->output) matches.push_back(idx);
}
return matches;
}
};
int main() {
ACAutomaton ac({"he", "she", "his", "hers"});
for (int idx : ac.search("ahishers"))
cout << "match: " << idx << "n";
return 0;
}
复杂度与总结
- 建 Trie：O(m)；建失败指针：O(m)（BFS 每个节点入队一次）；
- 匹配过程：O(n + z)，其中 z 是匹配成功次数（每次输出都要计入）；
- 总复杂度 O(n + m + z)，与模式串数量无关——这正是它比”每个模式串单独跑 KMP”（O(k·n)）优秀的地方。
AC 自动机是”Trie 组织模式串 + 失败指针复用匹配信息”的经典组合，多模式匹配场景下是性能最优的方案之一。
