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<std::pair> search(const std::string& text, TrieNode* root) { std::vector<std::pair> matches; // (起始位置, 模式串索引) TrieNode* curr = root;for (int i = 0; i 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树更安全。
以上就是C++怎么实现一个AC自动机算法_C++多模式字符串匹配与Trie图的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485621.html
微信扫一扫 
支付宝扫一扫 
