TrieNode 应用固定数组 children[256] 存子节点、根节点 fail 显式初始化为 nullptr、output 用 vector 存多模式索引；fail 构建需补全转移边并合并 output；匹配时须沿 fail 链向上收集结果。
直接用 std::map 或 std::unordered_map 存子节点，匹配性能会掉一截——高频场景下哈希开销和指针跳转是硬伤；固定数组（如 children[128]）才是 ASCII 场景下的首选。
怎么定义 TrieNode 才不崩在内存访问上
核心是三点：字符集决定存储结构、根节点 fail 必须显式初始化为 nullptr、output 必须支持多模式共尾。
- 别用
std::map存子节点——插入/查找都带哈希 + 跳指针，实测比固定数组慢 2–3 倍；纯 ASCII 场景（含控制符）用children[128]或更稳妥的children[256]；若需 Unicode，才切回std::unordered_map，且必须提前reserve(256)，否则插入时 rehash 会抖动 -
fail字段初始化不能漏：根节点构造函数里必须写fail = nullptr，否则 BFS 构建时trie[u].fail->nxt[c]解引用野指针 -
output别用bool isEnd或int patternId：像"he"和"she"共享结尾节点'e'，得用std::vector存所有匹配模式索引，否则漏结果 - 节点总数预分配要留余量：总字符数 ∑len × 1.2，否则
idx超界后trie[idx]访问越界——尤其插入长模式串或大量短串时容易爆
构建 fail 指针时 BFS 容易卡在哪
不是“父节点 fail 的子节点”，而是“从父 fail 出发，沿 children 找相同字符，找不到就继续跳 fail”，标准 BFS 实现里两个坑最致命。
-
trie[u].nxt[c]为空时不能跳过：必须设trie[u].nxt[c] = trie[trie[u].fail].nxt[c]—— 这叫转移边补全，否则匹配时每一步都要手动跳 fail 链，O(n) 变成 O(n×depth) - 设置完
fail[v]后，必须合并 output：output[v].insert(output[v].end(), output[fail[v]].begin(), output[fail[v]].end())，否则"hers"匹配时不会触发"he"和"she" - 根节点所有非空子节点的
fail必须设为根（即0或root），漏掉一个就会导致后续节点 fail 构建错乱 - BFS push 前必须确认
v存在：写成if (v) { ... q.push(v); }，别直接q.push(trie[u].nxt[c])，否则空指针入队，pop 后解引用崩溃
文本匹配时为什么总是漏结果或重复报告
只检查当前节点 output 是最大误区；正确做法是从当前节点出发，沿 fail 链一路向上收集，但要注意重叠边界。
- 匹配到位置 i 后，不能只看
cur->output：必须循环执行for (auto* p = cur; p; p = p->fail) { collect(p->output); }，否则"his"在"shis"里会漏掉 - 同一模式在同一起点不重复报告：AC 自动机天然按结束位置报告，
"aa"在"aaaa"中默认报告三次（位置 1、2、3 结束），无需额外去重；但若要求“非重叠”，就得在收集时加偏移判断 - 字符集不匹配会静默失败：比如用
children[26]却传入大写字母或数字，s[i] - 'a'下标越界——务必确保输入字符已规整（如tolower()或映射到 0–127） - 匹配循环中没处理空节点跳转：常见写法
cur = cur->children[c]前没判空，应改为cur = cur->children[c] ? cur->children[c] : root，否则空指针解引用
真正卡住人的从来不是算法逻辑，而是字符集选型、fail 链合并时机、output 收集路径这三处——它们不出错时 AC 自动机快得像线性扫描，出错时连单模式 KMP 都不如。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
