\(\text{AC}\) 自动机常用技巧汇总

参考文章：自动机相关 by Alex_Wei
相关题目与题解：杂题2022

1.\(\text{AC}\) 自动机上 \(\text{dp}\)

常用与限制长度与字典的字符串计数或权值最优化问题。
状态设计为 \(dp(l,u)\) 表示长度为 \(l\) 的字符串当前在自动机上匹配到 \(u\) 状态的方案数（或最优答案）。
转移考虑枚举当前状态的转移。
其他：

• 给定长度较大时，结合矩阵快速幂或倍增转移。
  例题：CodeForces-696D Legen...
• 给定模式串较少时，考虑状压。

2.\(\text{fail}\) 树相关操作

\(\text{fail}\) 树性质

\(\text{fail}\) 树是 \(\text{AC}\) 自动机的第二幅面孔，根据 \(\text{fail}\) 指针的定义，有如下性质：

• 有根树，根节点为 \(0\)，支持一切树上操作
• 如果某个模式串在状态 \(u\) 终止，那么其同样在 \(u\) 的子树中所有节点代表状态终止。
• 上一性质的另一说法是，树上每个节点都代表着其到根节点路径上的所有节点的终止集合。
• \(\text{fail}\) 树上的后缀关系是互推的，也就是说不存在一个不在子树内的节点和该节点后缀相同。

降低复杂度，减少常数的操作

把问题转化成 \(\text{fail}\) 树上问题后，由于链上问题多数为根链，我们可以减少 \(\log^2\) 的链上问题，转化为 \(\log\) 的单点或子树问题。
基本转化如下：

• 单点修改、根链查询转化为子树修改，单点查询
  有这样一类问题，每次将字典中已知的某个模式串移除或加入字典，并查询文本串的匹配次数。不难发现匹配过程中每到达一个节点就会其根链上的结尾状态个数，也就说每个节点都对子树有一个贡献，于是可以直接对子树做修改。
  例题：CodeForces-163E e-Government。
• 树上差分
  如果题目要求每个模式串匹配次数，即同一文本串多次匹配同一模式串算作多次，那么不需要考虑去重问题；而要求每个模式串匹配个数，即同一文本串多次匹配同一模式串算作一次，这时的贡献就需要精细统计。
  一次匹配实际上对是所有状态根链并的贡献，也就是这些匹配到的节点的虚树。将这些节点按照 \(\text{dfs}\) 序排序，每次对当前节点的根链 \(+1\)，当前节点与上一节点的 \(\operatorname{LCA}\) \(-1\)。
• 根链修改、单点查询转化为单点修改、子树查询
  和第一种转化恰好相反，尤其是当问题转化成树上差分时，根链修改可以再做一步转化。由对每个父亲都有贡献转化成对子树的查询。
  例题：洛谷-P5840 [COCI2015]Divljak。

总结一下：尽量避免修改或查询父亲，将对贡献的对象直接修改转化成对贡献的来源直接查询。
实际上以上操作对于普通的树上问题同样具有参考价值。

3.处理前缀后缀、正串反串

发现 \(\text{AC}\) 自动机是正序匹配，也就是每次是对文本串前缀做匹配，匹配到的是模式串的后缀。遇到与之相反的问题可以考虑对模式串建反串 \(\text{AC}\) 自动机，对文本串的反串匹配。
例题：CodeForces-1202E You Are Given Some Strings...

4.字符串问题直接变为序列问题

将文本串匹配过程记录下来，就变成了经典序列问题，如最小区间覆盖等等。
例题：P7456 [CERC2018] The ABCD Murderer