AC自动机通过构建Trie树并引入失败指针实现多模式匹配，利用BFS构造fail指针以避免回溯，从而在O(n + m + k)时间内完成文本扫描，适用于敏感词过滤等场景。
AC自动机（Aho-Corasick算法）是一种高效的多模式字符串匹配算法，适合在一段文本中同时查找多个关键词。它基于Trie树结构，并引入类似KMP算法的失败指针（fail pointer），实现状态间的快速跳转，从而达到线性时间复杂度的匹配效率。
构建Trie树
将所有模式串插入到Trie树中，每个节点代表一个字符，路径从根到叶构成一个完整的模式串。插入时记录每个单词的结束位置，用于匹配输出。
- 定义Trie节点：包含子节点指针数组、是否为单词结尾、匹配的模式串索引等信息
- 逐个插入模式串，每一步创建必要节点
- 标记最后一个节点为终止节点，并保存对应模式串的编号或内容
示例节点结构：
struct TrieNode {
std::map children;
bool isEnd;
int patternIndex; // 可选：记录是哪个模式串
TrieNode* fail;
std::vector output; // 存储在此结束的所有模式串索引
TrieNode() : isEnd(false), patternIndex(-1), fail(nullptr) {}};
构造失败指针（Fail指针）
失败指针的作用是在当前匹配失败时，跳转到最长公共后缀对应的节点，避免回溯文本指针。通过广度优先遍历（BFS）构造fail指针，类似于KMP中的next数组思想。
立即学习“C++免费学习笔记（深入）”；
- 根节点的fail指针指向空或自身
- 对每个节点的子节点，尝试继承父节点fail链上的第一个能匹配该字符的节点
- 如果找不到，则继续沿fail链上溯，直到根为止
- 使用队列进行层序遍历完成整个Trie图的构建
关键代码片段：
void buildFailPointer(TrieNode* root) {
std::queue q;
root->fail = nullptr;
q.push(root);
while (!q.empty()) {
TrieNode* curr = q.front(); q.pop();
for (auto& [ch, child] : curr->children) {
TrieNode* f = curr->fail;
while (f && f->children.find(ch) == f->children.end()) {
f = f->fail;
}
if (f && f->children.count(ch)) {
child->fail = f->children[ch];
} else {
child->fail = root;
}
// 合并输出：若fail链上有结束节点，也加入output
if (child->fail) {
child->output.insert(child->output.end(),
child->fail->output.begin(), child->fail->output.end());
}
q.push(child);
}
}}
执行多模式匹配
文本扫描过程中，从根节点开始，根据字符转移状态。若无子节点，则通过fail指针回跳，直到可以前进或回到根节点。每当进入一个节点时，检查其output列表，若有内容则表示发现匹配。
- 逐字符读取主串，动态更新当前状态节点
- 每次访问节点后，检查output是否有匹配项
- 可记录匹配位置和对应模式串
匹配函数示例：
std::vector> search(const std::string& text, TrieNode* root) {
std::vector> matches; // (起始位置, 模式串索引)
TrieNode* curr = root;
for (int i = 0; i < text.size(); ++i) {
char ch = text[i];
while (curr && curr->children.find(ch) == curr->children.end()) {
curr = curr->fail;
}
if (curr && curr->children.count(ch)) {
curr = curr->children[ch];
} else {
curr = root;
}
// 输出所有在此结束的模式串
for (int idx : curr->output) {
matches.emplace_back(i - patterns[idx].size() + 1, idx);
}
}
return matches;}
基本上就这些。AC自动机构建完成后，能在O(n + m + k)时间内完成匹配，其中n是文本长度，m是所有模式串总长，k是匹配总数。适用于敏感词过滤、关键词高亮、日志分析等场景。注意内存管理，尤其是节点释放。使用智能指针或手动析构清理Trie树更安全。
