概述
用于解决多模式串匹配问题。
将模式串插入 trie 中，对每个点构造 $fail$ 指向模式串中与其后缀匹配的最长前缀。
以每个点的 $fail$ 为父节点构建 fail 树，满足节点 $x$ 对应的串为节点 $y$ 对应的串的后缀当且仅当 $y \in T(x)$。
例题
1.AC 自动机（简单版）
出现过，遍历后就赋值为 $-1$，遇到 $-1$ 则停止，查询时间复杂度线性。
2.【模板】AC 自动机
将文本串对应的所有节点标记，相当于查询子树和。
3.[HNOI2004] L 语言
DP，记 $f_i$ 为 $i$ 前缀是否合法，转移形如 $f_i|=f_j([j+1,i] \in D)$，由于 $|s| \le 20$，对 trie 上每个节点维护二进制状态表示长为 $k$ 的模式串是否出现即可 $O(1)$ 转移。
4.[COCI2015] Divljak
将 $S$ 插入 trie 中，建立 ACAM。相当于单点加颜色，查询子树中颜色种类数。对每个点维护子树中颜色种类数，每次是链并的加，按 dfs 序排序后，容斥一下即可。可以再差分用树状数组维护。