AC自动机适合多模式串批量匹配场景，如敏感词过滤、日志高亮、模板渲染；需构建紧凑Trie、BFS构造fail指针、预分配buffer替换、按权重排序合并重叠区间；推荐轻量单头库ac-trie。
AC自动机适合什么场景？
当你需要在一段长文本中，同时查找并替换多个固定字符串（比如敏感词过滤、日志关键词高亮、模板变量批量渲染），且模式串数量在几十到上万级别时，AC自动机比反复调用 std::string::find 或正则快一个数量级。它把所有待查模式构建成一棵带失配指针的 Trie，单次扫描主串就能完成全部匹配。
手写 AC 自动机要注意哪几个核心点？
标准教材实现常忽略实际工程约束，导致内存爆炸或替换错位。关键控制点如下：
-
节点结构必须紧凑：避免
std::map<char node></char>，改用std::array<node></node>（ASCII 场景）或unordered_map<char node></char>（Unicode 需转 UTF-8 处理）；每个节点额外存fail指针和output（匹配到的模式索引列表） - 构建 fail 指针必须用 BFS，不能 DFS：否则深度过大时栈溢出，且无法保证层级顺序；队列初始化时把根节点所有非空子节点入队，再逐层处理
-
替换时不能原地修改 string：C++
std::string修改会触发多次内存拷贝；正确做法是预分配结果 buffer，用std::vector<size_t></size_t>记录所有匹配位置和长度，最后按从后往前顺序拼接
如何避免多模式重叠导致的替换冲突？
比如模式串含 "ab" 和 "abc"，主串为 "abc"，若先替换了 "ab"，后续就找不到 "abc"。AC 自动机本身能同时报告所有匹配，但替换逻辑需显式处理优先级：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 构建时给每个模式串打权重（如长度优先、或按输入顺序倒序），存入节点的
output中 - 匹配过程中收集所有命中区间
[start, end)，用std::vector<:tuple size_t>></:tuple>存（起始、结束、权重），最后按权重排序去重 - 去重规则：若区间 A 完全包含 B，且 A 权重 ≥ B，则丢弃 B；若重叠但不包含（如
"ab"和"bc"），保留两者，替换时按位置顺序插入，靠 buffer 偏移量避免覆盖
有没有现成可用的轻量级 C++ 实现？
Boost 里没有 AC 自动机，aho_corasick 库（GitHub 上同名）太重且依赖 Boost.Iterator；推荐直接集成 zlib 风格的单头文件实现：ac-trie（仅 300 行），它支持自定义 allocator、禁用 RTTI，且输出接口返回 std::span<const int></const>（匹配 ID 列表），方便你绑定自己的替换映射表。
立即学习“C++免费学习笔记（深入）”；
注意：该库默认不处理重叠，你需要在外层加一层区间合并逻辑——这恰恰是批量替换中最容易被跳过的环节，也是线上出现漏替换或错替换的主因。
