应使用ac自动机而非kmp套循环，多模式串时性能优势显著；trie节点优先用固定数组（如next[26]）而非map以保证o(1)访问和内存局部性；buildfail()中else分支实现trie图优化，使匹配免去while跳转；需沿fail链传播output以捕获所有后缀匹配。
直接用 AC automaton，别手写 KMP 套循环——多于 3 个模式串时，性能差距立刻拉满。
为什么不能直接用 map 做 Trie 节点
看似灵活，实则在高频匹配中拖慢 2–3 倍：每次 children.find(c) 是 O(log k)；而固定字符集（如小写 a–z）用 next[26] 是 O(1) 数组访问。更关键的是，map 会破坏内存局部性，cache miss 显著上升。
- 只在字符集极不规则（比如 Unicode 混合符号）且模式串极少时才考虑
map或unordered_map - 若需支持大小写+数字，用
next[128]（ASCII 范围）比动态结构更稳 -
std::vector<:pair node>></:pair>查找仍是线性，比map还差，别踩
buildFail() 中的 else 分支：trie[u].nxt[c] = trie[trie[u].fail].nxt[c] 是干啥的
这是构建「Trie 图」（Trie with failure transitions）的关键一步：把原本空的子指针，直接指向 fail 链上第一个能响应字符 c 的节点。它让匹配过程彻底免去 while 循环跳 fail 指针的开销。
- 没有这行，匹配时就得写
while (v && !trie[v].next[c]) v = trie[v].fail，最坏退化成 O(n × depth) - 有这行，
u = trie[u].next[c]一步到位，后续匹配全是 O(1) 跳转 - 注意：这行必须放在
if (v)分支之外，否则空指针不会被压缩
匹配阶段漏掉 output 链传播？你可能只找到最长匹配
isEnd 标记只能捕获「以当前节点结尾」的模式串，但 AC 自动机要求输出所有后缀匹配——比如文本是 abcc，模式串含 bc 和 c，到第二个 c 时必须同时报告两个。
- 正确做法：每个节点存
output字段（std::vector<int></int>或位掩码），构建 fail 时做合并：node.output.insert(node.output.end(), fail_node.output.begin(), fail_node.output.end()) - 更省内存的做法：匹配时不存完整列表，而是在
query()中沿 fail 链向上遍历并收集，但要加 visited 缓存防重复 - 千万别只靠
isEnd+ 单次判断——那是普通 Trie，不是 AC 自动机
fail 指针的语义不是“跳到某个单词”，而是“跳到当前路径的最长真后缀所对应的节点”；这个后缀本身未必是完整模式串，但它承载了所有以此为后缀的模式串信息。理解这点，才能不把 buildFail() 写成黑箱。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
