AC自动机的核心结构需按字符集选择存储：ASCII用固定数组（ALPHABET_SIZE=128/256），Unicode用预分配bucket的unordered_map；根节点fail必须初始化为nullptr；output须用vector支持多模式共尾；节点总数预留20%余量；fail构建需补全转移边并合并output；匹配时须遍历整条fail链收集结果。
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"。
- 根节点所有非空子节点的
fail必须设为根，不能漏 - 队列 push 前要确认
v存在，否则trie[v].fail解引用崩溃 - fail 构建完立刻验证：对任意节点
u，depth[fail[u]] < depth[u]必须成立，否则循环依赖
文本匹配时怎么避免重复触发和漏匹配
常见错误是只检查当前节点 output，却忽略 fail 链上所有可输出节点。正确做法是匹配到位置 i 后，从当前节点出发，沿 fail 指针一路向上，每到一个节点就收集其 output，直到 fail == nullptr。但要注意：同一模式在同一起点不能重复报告（比如 "aa" 在 "aaaa" 中出现三次，但 AC 自动机默认只报告每个结束位置一次）；若需重叠匹配（如 "aa" 在 "aaa" 中匹配两次），必须在插入时允许模式串共享中间节点，且匹配时不提前终止 fail 链遍历。
- 用
std::vector<bool> visited标记已报告的 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 是状态变量，必须每个线程独占一份或加锁。
立即学习“C++免费学习笔记（深入）”；
- 调试时打点：统计
fail跳转总次数 / 文本长度，若 > 1.5，说明 fail 树结构差，需检查插入顺序（短模式优先插入能降低 fail 深度） - 内存对齐：TrieNode 里把指针放前面、int 放后面，避免 padding 浪费空间
- 静态构建后，可把整个 trie 序列化成连续数组，减少 cache miss
