AC 自动机学习笔记
前言AC自动机（\(Aho\ Corasick\ Atomaton\)）有着一种 \(KMP\) 的思想，所以在学习之前建议先学一下 \(KMP\)。同时还需要了解一下 \(Trie\) 树（建议去看一下 oi-wiki 上的字典树）
问题描述
给定一个字符串 \(S\) 和 \(n\) 模式串，问有多少个模式串在 \(S\) 中出现过。
首先我们把 \(n\) 个模式串组成一个 \(Trie\)（就当你们学会了 \(Trie\) 树）
https://img2023.cnblogs.com/blog/3191634/202308/3191634-20230829135048507-1597132835.png
模式串：\(ABC,BCD,BD,C\)，其中绿色的点表示字符串的结尾。
对于 \(|S|=ABCBCD\)，那么我们在 \(Trie\) 上开始匹配，最开始会经过 \(2,3,4\) 三个点到 \(4\) 的时候，发现已经成功匹配了一个模式串了，那么现在我们需要从根在匹配一次吗？
显然的，不需要，\(KMP\) 的思想可以运用在这个 \(Trie\) 树上，我们在匹配完 \(4\) 的时候可以直接来到 \(7\) 然后再匹配到 \(8\)。
对于从 \(4\) 到 \(7\) 这个步骤，我们称 \(7\) 是 \(4\) 的 \(Fail\)（失配指针）。
\(Fail\) 指针
刚才说了 \(Fail\) 是失配指针，那么如果此时匹配失败，那么就到达这个指针指向的位置，所以，失配指针指向的节点是当前节点所代表的串，最长的、能与后缀匹配的，且在 \(Trie\)
中出现过的前缀所代表的节点。
我们设点 \(x\) 的父亲的 \(Fail\) 指针指向的是 \(p\)，那么如果 \(p\) 的儿子 \(y\) 和 \(x\) 相同，那么 \(x\) 的 \(Fail\) 指针指向的就是 \(y\)（应该挺好理解的吧）。
那么如果没有儿子呢？
那就再造一个儿子，就把当前节点的子节点指向当前节点的 \(fail\) 节点的子节点。
而且发现每个点 \(fail\) 指向的节点都比当前节点小，那么第二层的 \(fail\) 就指向根节点。
然后对于失配指针 \(Fail\) 我们需要使用 \(BFS\) 来实现。
inline void Get_fail(){ for(int i=0;i
页:
[1]