1. AC 自动机 ACAM
1.1. 介绍
AC 自动机用于解决多模式串匹配问题，例如求多个模式串在文本串中的出现次数。显著地，它的应用实际上非常广泛。
借助 KMP 的思想，我们对 Trie 树上的每个节点构造其失配指针 \(fail_i\)，指向对于当前字符串的最长后缀（其他（前缀）作为当前串后缀的最长的一个），显著地，每个节点的失配指针都指向一个更短的状态。当这样的后缀不存在时，失配指针会指向表示空串的根节点。
考虑如何构建 \(tail_i\)：
根据每个节点的失配指针都指向一个更短的状态这个性质，考虑用 BFS 解决 \(tail_i\) 的构建，对于当前节点 \(now\) 来说，假设深度较小的节点都已经被处理完了。
现在假设当前节点 \(i\) 由 \(fa_i\) 经过字符 \(ch\) 转移过来，使 \(tail_i\leftarrow trans(fail_{fa_i},ch)\)，若不存在 \(fail_{fa_i}\) 通过 \(ch\) 转移到的某一节点，则尝试使 \(fail_i\leftarrow trans(fail_{fail_{fa_i}},ch)\)。直到 \(fail\) 指向根节点，说明根本不存在合法前缀，我们使 \(fail_i\leftarrow rt\)。
特殊地，若不存在 \(trans(fa,ch)\) 这个转移方式，则直接令 \(trans(fa,ch)\leftarrow trans(fail_{fa_i},ch)\)。
1.2. 常见技巧
1.2.1 \(fail\) 树的性质
构建的 \(fail\) 指针会形成一棵树，称为 \(fail\) 树。这不是废话吗。
- \(fail\) 树为一颗有根树，可以进行树剖等树上操作。
- 对于节点 \(p\) 与其对应字符串 \(t_p\)，对于任意一个子树内节点 \(q\)，都有 \(t_p\) 是 \(t_q\) 的后缀。逆命题亦成立。
- 设 \(cnt_p\) 表示作为 \(t_p\) 后缀的字符串数量。若无重复串，则 \(cnt_p\) 为树上节点 \(p\) 到根节点上字符串节点数量。
1.2.2 应用
ACAM 可以与 DP 结合，在自动机中进行 DP。
2. 后缀自动机 SAM
咕咕咕
标签：ch,fa,后缀,Note,fail,字符串,自动机,节点 From： https://www.cnblogs.com/Eon-Sky/p/17631535.html