OI-wiki Link and bilibili Link
AC 自动机，主要用于解决多模式串(即需要求出出现次数等的串)匹配的问题，基于字典树。
大致
将模式串建到字典树上，对每个字典树上的节点求出失配指针，根据失配指针建立失配树，用失配树来维护模式串出现次数。
具体构建
建立字典树
略。
失配 fail 指针
失配指针用于辅助多模式串匹配。
节点 \(x\) 的失配指针意思是其对应字符串 \(s\) 的最长可匹配(在字典树中能找到)后缀对应字典树的哪个节点。
由于是最长可匹配后缀，那么我们可以发现，只要我们不断枚举 fail[x], fail[fail[x]] ...，就可以把其每个可匹配后缀都枚举出来。
当字典树上一个节点 \(x\) 在后接一个字符 \(c\)、转移至 \(y\) 时(假设已经求出了 \(x\) 的 fail 指针)，只需要枚举每个 \(x\) 的每个可匹配后缀，判断在其后面加上 \(c\) 是否有对应的节点即可。
但这样做的复杂度似乎不太对，考虑优化。
路径压缩优化(字典图)
为了避免反复枚举一个转移 \(a \xrightarrow{c} b\)，可以按照深度去求 fail。枚举 \(x\) 和后接的一个字符 \(y\) 时，如果 \(x\) 没有一个 \(y\) 转移，则记录 \(trie_{x,y}=trie_{fail_x, y}\)，将路径压缩存储下来，否则就更新 \(fail_{trie_{x,y}}=trie_{fail_x,y}\)。
由于这个操作改变了字典树的结构，所以也被称为建立字典图。
建立 fail 树
求出 fail 后，一般都需要用 fail 树来辅助维护答案。
顾名思义，就是以 \(fail_x\) 为 \(x\) 的父亲搭建出的一棵树，其性质是如果 \(x\) 对应字符串被成功匹配了一次，那么其父亲也必然会被成功匹配一次，可以用求子树内权值和的方式来求出现次数。
至此，AC 自动机的前置搭建已经完成，那么就是处理匹配的问题了。
处理匹配
仍然是在字典图上面处理，求出答案后把标记打在失配树上，最后用失配树来处理答案。
假设现在匹配到了 \(x\) 这个节点，后接一个字符 \(y\)，如果字典图上有这个转移则直接转移过去，否则转移到 \(trie_{fail_x,y}\) 去，每接一个字符都要记得在失配树上对应节点打上一个标记。
最后求答案即可。