ac自动机核心是trie树加bfs构建的fail指针：节点含子节点容器、is_end、fail指针和output；fail必须在全部模式插入完成后用bfs构造，根子节点fail指向根，其余节点通过跳转fail链查找对应子节点；匹配时需沿fail链回溯检查所有is_end以捕获重叠匹配。
AC自动机核心结构怎么建：节点设计和fail指针构造
AC自动机本质是Trie树 + BFS构建的fail指针，不是直接套用现成库——C++标准库不提供。必须手写TrieNode，每个节点存子节点数组（或unordered_map<char trienode></char>）、是否为结尾（is_end）、fail指针、以及可选的output（用于记录该节点匹配到哪些模式）。
fail指针构造必须用BFS（队列），不能DFS：根节点所有子节点的fail指向根；之后每弹出一个节点cur，遍历其子节点c：若cur->children[c]存在，则其fail = cur->fail->children[c]（若后者为空，则继续跳fail，直到根或找到）；若cur->fail->children[c]不存在，就回退到根。这个“跳fail找子”的过程必须循环处理，否则会漏掉深层匹配。
- 用
vector<trienode> children(256, nullptr)</trienode>适合ASCII敏感词；若含Unicode（如中文），必须改用unordered_map<char32_t trienode></char32_t>并统一转UTF-32 -
fail指针初始化必须为nullptr，且BFS前要把根节点所有非空子节点入队，再设它们的fail为根 - 别在插入时就建fail——必须等所有模式插入完，再统一BFS构建，否则fail链不完整
怎么批量插入敏感词：避免重复清空与内存泄漏
插入就是标准Trie插入：从根出发，对每个字符c，若cur->children[c]为空则新建，最后在末尾节点设is_end = true，并可存原始词（如word字段）或ID。关键点在于——不要每次插入都delete整棵树；应该只在析构函数里递归释放，且用智能指针（unique_ptr）更安全。
- 插入中文时，若用
string直接遍历char会按字节切分，导致乱码匹配；必须先用std::wstring_convert或第三方UTF-8解码（如utf8cpp）转成vector<char32_t></char32_t>再插 - 如果多个模式有公共后缀（如"中国"和"中国人"），AC自动机会自然复用路径，但需确保"中国"的节点也标记
is_end，不能只标最长词 - 插入后不要立即调用
build_fail()——等全部插完再调一次，否则时间复杂度退化
怎么执行匹配：单次扫描+fail跳转，别漏掉重叠匹配
匹配文本时，从根开始，对每个字符c，不断沿fail向上跳，直到当前节点有children[c]，然后走过去。到达新节点后，要检查它自身及所有沿fail链向上的节点是否is_end——因为AC自动机支持“输出所有匹配”，不是只报最长那个。例如文本"ababc"匹配模式"ab"、"babc"、"abc"，必须全捕获。
- 实际代码中，不能只检查当前节点：要while循环
temp = temp->fail，只要temp != nullptr就检查temp->is_end，否则漏掉"ab"在"ababc"中的第二次出现 - 若只需返回是否存在匹配，遇到第一个
is_end即可返回true；若需定位位置，得在节点里存length或起始索引偏移 - 大文本匹配时，避免频繁字符串拼接：用
std::string_view传入待匹配文本，用下标而非substr减少拷贝
常见崩溃和性能坑：空指针、编码错位、fail未初始化
最常触发Segmentation fault的是访问空fail指针——比如没把根节点的子节点fail设为根，后续跳fail时直接解引用nullptr。另一个高频问题是UTF-8误当ASCII处理：一个中文字符被拆成3个char，导致插入/匹配路径完全错乱，表现是“明明加了词却永远不命中”。
- 调试时打印任意节点的
fail路径（如node->fail->fail->...->nullptr），确认长度合理；根节点的fail必须为nullptr，且所有叶子节点的fail不能指向自己 - 用
valgrind或ASan跑一遍插入+匹配流程，重点看TrieNode构造/析构是否成对，避免野指针 - 百万级敏感词时，纯vector子节点（256大小）内存爆炸，必须切到
unordered_map；但map查找慢，可考虑robin_hood::unordered_map替代
AC自动机的正确性极度依赖fail指针的拓扑顺序和BFS构造时机，任何一步跳过初始化或提前构建都会让整个匹配逻辑静默失效——它不会报错，只是漏匹配。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
