ACAM

KMP 例：在a串中查找b串的位置。（len <= 1e6） O(n2)的暴力是好想的。两层循环，第一层遍历a串，第二层遍历b串，对应比较即可。 但我们会发现对于a串，我们每次都不断将循环变量i右移，可匹配失败后，又将i返回至右移之前的位置。 太劣了，所以我们选择取消i的返回操作，每次用b串去匹配a ......

怎么有人现在才学 ACAM 呢。 好像比 SAM 简单挺多啊，也不记得当时是哪里看不懂。 AC 自动机（✔） 自动 AC 机（✘） 概述 ACAM(Aho–Corasick Automaton)，是用来解决多模式串匹配的字符串算法。它的结构是个 DAG，其中点表示状态，边表示转移。这一点上各种自动机 ......

## AC自动机 ### 定义 定义 `trie` 树上的节点代表其形成的前缀 令 `fail` 树为 `trie` 树上的节点向被 `fail` 指针指向当前节点的点连边，形成的以 `trie` 树的根为根的树 $son[\,i\,][\,now\,]$ 为 $now$ 节点后加入字符 $i$ 的 ......

首先，显然答案等于 $[1,r]$ 中符合条件的子串个数减去 $[1,l-1]$ 中符合条件的子串个数减去跨 $l-1,l$ 的子串个数。前面两部分的处理是容易的，直接建出 ACAM 然后每加入一个字符就在上面条转移边即可。 考虑怎么处理跨中间的贡献。相当于我们要找 $[1,l-1]$ 的一段后缀与 ......