什么是 AC 自动机
AC 自动机（Aho-Corasick）1975 年由 Alfred Aho 和 Margaret Corasick 提出，解决多模式匹配：给定一组模式串，一次扫描主串找出所有模式串的所有出现位置，复杂度 O(n + m + z)（n 主串长、m 模式串总长、z 命中次数）。
适用场景：敏感词过滤、病毒特征码扫描、DNA 序列多模式查找、代码扫描器。
三件套：Trie + 失败指针 + 输出
- Trie 树：所有模式串插进一棵字典树，公共前缀共享路径；
- 失败指针（fail）：类似 KMP 的 next——当前节点无对应子边时，沿失败指针跳到”最长真后缀”对应的节点，不回到根重来；
- 输出（output）：每个节点记录”走到这里命中哪些模式串”。
失败指针的语义：节点代表一个前缀串，它的 fail 指向该串的最长真后缀对应的节点。比如 “hers” 的 s 节点，最长真后缀是 “s”（”she” 的开头），所以 fail 指向 she 的 s 节点——匹配 her 后失配，还能顺带用上已经扫过的后缀。
构建步骤
1. 建 Trie
把每个模式串逐字符插入，末尾节点记下模式串编号。复杂度 O(m)。
2. BFS 建失败指针
规则：根的子节点 fail 指向根；其余节点，看父节点的 fail 是否有同字符子节点——有就指向它，没有就继续沿 fail 链向上，直到根。逐层 BFS，每个节点只入队一次，O(m)。
3. 合并输出
一个节点的输出 = 自身结尾的模式串 ∪ 失败指针链上所有节点的输出。建 fail 时直接把 fail 节点的输出并进来，匹配时就不用再跳链收集。
匹配过程
从根开始逐个读主串字符：有子边走子边；没有就沿 fail 跳，跳到根还没有，则从根重新开始（当前字符匹配不上）。
示例：主串 "ahishers"，模式串 ["he","she","his","hers"]：
'a': 根没有 a 子边，停在根
'h': 进入 h 节点
'i': 进入 i 节点
's': 进入 s 节点，输出 "his"；沿失败链到 s(she)，输出 "she"
'h': s(his) 无 h 子边，沿失败指针到 s(she)，再走 h 子边进入 h
'e': 进入 e 节点，输出 "she"；失败链上的 e(he) 输出 "he"
'r': e(she) 无 r 子边，沿失败指针到 e(he)，走 r 子边进入 r
's': 进入 s 节点，输出 "hers"；失败链上的 s(she) 输出 "she"
命中：his（1-3）、she（4-5 与 5-6）、he（5-6）、hers（4-7）
完整代码（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)，匹配 O(n + z)——总 O(n + m + z)，与模式串个数无关；
- 对比”每个模式串单独跑 KMP”的 O(k·n)，模式串多时优势明显；
- AC 自动机是”Trie 组织模式串 + 失败指针复用匹配信息”的经典组合，多模式匹配场景的首选。
