AC 自动机

AC 自动机是更高维的 kmp。构造方法感觉更像是运用了 dp 的思想，先对所有模式串建立一棵 Trie 树，然后考虑某个节点 \(x\)，有个 \(w\) 的后缀，考虑如何去求它的 fail 值。于是就有了 AC 自动机的核心代码：

int x=q.front(),ff=t[x].fail;q.pop();
for(int i=0;i<26;i++)
	if(t[x].nxt[i])t[t[x].nxt[i]].fail=t[ff].nxt[i],q.push(t[x].nxt[i]);
	else t[x].nxt[i]=t[ff].nxt[i];

单纯匹配的题有 第一块板子。

比较无脑的就是可以在 AC 自动机上 DP，和在 kmp 自动机上 DP 是同一个道理。P4052 是板子，套路是以当前匹配到的位置 \(x\) 作为状态进行转移，决策就是下一个字符放啥，然后正常转移即可，在这道题中的限制就是不能转移到有 end 的节点，把这些点忽略即可。显然它是可以用矩阵来描画的，P3041 是矩阵快速幂优化 DP 套 AC 自动机，缝合题。P7456 不能算是 AC 自动机上 DP，而只能算是帮助 DP，不知道应该归到哪里。

一般的题目都会用到 fail 树的性质。自动机上每个点往 fail 对应的点上连边，显然最后会形成一棵树（每个点只会往更浅的点连接）。有一个显然的性质是，对于一个节点 \(x\)，它到根的路径可以看成是 kmp 的一个匹配过程，所以实际上这些点的串都是 \(x\) 串的后缀，这就非常有用了。在 第二块板子 中，我们现在停留在 \(x\)，那么实际上达到的效果是点到根所有点对应的串都出现了一次，然而暴力去找显然是不行的。于是可以找每个点出现的次数，然后回答的时候可以看成是一次子树求和（因为子树内的值会对它产生贡献）。P3966 也是一个意思。

fail 树也是树，所以可以树剖，这牵扯到一个性质。首先根据字典树的原理，一个节点在字典树上到根的所有节点形成了它的前缀集合，而一个串在另一个中出现可以看成前者是后者前缀的后缀。而前面也说了，\(A\) 是 \(B\) 后缀表现为在 fail 树上 \(B\) 是 \(A\) 子树中的节点，所以要统计一个串在另一个串中出现了几次，就只需要把后者到根（字典树上）的所有点标记一下，然后查找前者子树中有多少个标记节点即可，用树状数组可以维护。P2414 就是这个方法，一个结论是说对于题目中所言的过程，虽然串的总长度可能很大，但建出来的 Trie 树不会太大（甚至可以边输入边建树）。把所有 \(y\) 离线下来排序之后按顺序回答就可以保证修改的次数是线性的，这样一来就可以用上面那种方法了，复杂度有一只 log。CF163E 会更简单一些，当前匹配到的点的贡献是 fail 树上点到根的权值之和，所以说修改操作就是单点修改，询问就是链查询，转化成子树修改单点查询即可，树状数组维护，一只 log。