2020-2021:teams:hotpot:ac自动机
这是本文档旧的修订版！
AC自动机
引入
$AC$ 自动机是一种多模式串匹配算法，一般用于解决对于在文本串中匹配一系列模式串（例：给一个文本串和一系列模式串，问模式串在文本串中一共出现了多少次）
实现方法
具体的实现方法我们可以参考 $KMP$，在每次匹配失败了之后，则需要从 $i$ 回到 $fail(i)$，即 $fail(i)$ 位置的前缀的是 $i$ 这个位置的前缀的后缀。
而 $AC$ 自动机则是在 $trie$ 上实现这样的操作。
如图所示
2020-2021/teams/hotpot/ac自动机.1597999299.txt.gz · 最后更改: 2020/08/21 16:41 由 lotk
