CVBB ACM Team

$AC$ 自动机是一种多模式串匹配算法，一般用于解决对于在文本串中匹配一系列模式串（例：给一个文本串和一系列模式串，问模式串在文本串中一共出现了多少次）

具体的实现方法我们可以参考 $KMP$，在每次匹配失败了之后，则需要从 $i$ 回到 $fail(i)$，即 $fail(i)$ 位置的前缀的是 $i$ 这个位置的前缀的后缀。

而 $AC$ 自动机则是在 $trie$ 上实现这样的操作。

如图所示

设 $i$ 的父亲为 $i'$，指向$i$点的边上的字母为$c$

显然，当 $fail(i')$ 有字母 $c$的出边时，该出边的指向的点即为 $fail(i)$。（图中 $fail(7)=1,fail(8)=2$）

否则，我们就应当沿着 $fail$ 函数一直向上寻找，直到找到为止，如果找不到一个符合条件的点，则 $fail(i)$ 为根。（图中fail(3)=0）