C++如何实现字符串的高效多模式匹配(AC自动机)-C++-PHP中文网

ac自动机的核心结构需按字符集选择存储：ascii用固定数组（alphabet_size=128/256），unicode用预分配bucket的unordered_map；根节点fail必须初始化为nullptr；output须用vector支持多模式共尾；节点总数预留20%余量；fail构建需补全转移边并合并output；匹配时须遍历整条fail链收集结果。

c++如何实现字符串的高效多模式匹配(ac自动机)

AC自动机的核心结构怎么定义才不踩内存坑

直接用 std::map<char trienode></char> 存子节点看似灵活，但高频匹配下哈希开销和指针跳转会拖慢速度；固定数组（如 children[26]）更高效，但只适用于纯小写字母。实际项目里，得按字符集范围选：ALPHABET_SIZE 设为 128 可覆盖 ASCII，设为 256 更稳妥；若需支持 Unicode，必须切回 std::unordered_map，但得预分配 bucket 数（reserve(256)），否则插入时 rehash 会导致性能抖动。

根节点必须显式初始化 fail 为 nullptr，否则 BFS 构建时访问野指针
output 字段别只存 bool，得用 std::vector<int></int> 或 std::vector<:string_view></:string_view>，因为多个模式可能共用同一结尾节点（如 "he" 和 "she" 都在 'e' 结束）
节点总数预估要留余量：总长度 ∑len × 1.2，否则 idx 超界后 trie[idx] 访问越界

构建 fail 指针时 BFS 的关键逻辑在哪

失败指针不是简单“父节点 fail 的对应子节点”，而是“从父节点的 fail 出发，沿其 children 找相同字符，找不到就继续跳 fail，直到根”。标准写法是用队列做层序遍历，但容易错在两处：trie[u].nxt[c] 为空时，不能跳过，而应设 trie[u].nxt[c] = trie[trie[u].fail].nxt[c] —— 这叫“转移边补全”，避免匹配时反复跳 fail；另一处是设置完 fail[v] 后，必须把 v 的 output 合并进 fail[v] 的 output（即 output[v].insert(output[v].end(), output[fail[v]].begin(), output[fail[v]].end())），否则 "hers" 匹配时漏掉 "he" 和 "she"。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

根节点所有非空子节点的 fail 必须设为根，不能漏
队列 push 前要确认 v 存在，否则 trie[v].fail 解引用崩溃
fail 构建完立刻验证：对任意节点 u，depth[fail[u]] 必须成立，否则循环依赖

文本匹配时怎么避免重复触发和漏匹配

常见错误是只检查当前节点 output，却忽略 fail 链上所有可输出节点。正确做法是匹配到位置 i 后，从当前节点出发，沿 fail 指针一路向上，每到一个节点就收集其 output，直到 fail == nullptr。但要注意：同一模式在同一起点不能重复报告（比如 "aa" 在 "aaaa" 中出现三次，但 AC 自动机默认只报告每个结束位置一次）；若需重叠匹配（如 "aa" 在 "aaa" 中匹配两次），必须在插入时允许模式串共享中间节点，且匹配时不提前终止 fail 链遍历。

用 std::vector<bool> visited</bool> 标记已报告的 pattern ID，比每次查 set 快
文本扫描中，u = trie[u].nxt[c] 前必须先判空：若为空，u = trie[u].fail 再试，否则直接崩
字符 c 超出预设范围（如设了 26 却遇到 'A'）时，应 fallback 到根节点，而非跳 fail

性能瓶颈通常卡在哪儿

90% 的慢案例来自三处：一是 std::string 传参未用 std::string_view，导致每次 insert 都拷贝；二是 fail 链太长（平均深度 > 5），此时应做路径压缩（即把 fail[u] 直接指向 fail[fail[u]] 的有效输出节点，而非逐级跳）；三是多线程下共享同一个 AC 自动机实例，而 ac_query() 里的 u 和 visited 是状态变量，必须每个线程独占一份或加锁。