RainAir
My OI Blog
RainAir
AC 自动机学习笔记
AC 自动机学习笔记

定义

首先简要介绍一下 AC 自动机:Aho-Corasick automation,该算法在 1975 年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出 n 个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂 AC 自动机,先得有模式树(字典树)Trie 和 KMP 模式匹配算法的基础知识。KMP 算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。
如果您还不会 KMP,点击这里
如果您还不会 Trie 树,点击这里
好了,默认您已经掌握了两种基础算法,正文开始。
首先如果一个模式串一个匹配串问模式串出现了几次?可以使用 $O(n+m)$ 的 KMP 算法来解决。但是有多个模式串怎么解决呢?显然直接跑很多次 KMP 是不切实际的,那么我们就要考虑用一种更加方便的方法来将这些模式串联系起来,于是我们就可以考虑将两者结合起来。

建立字典树

假设我们有这些单词:she,he,say,her,shr,我们可以构造一颗字典树:
https://blog.aor.sd.cn/wp-content/uploads/2018/12/1149206-20171205083201206-2103041459.png

构造 fail 指针

这里是整个 AC 自动机的核心部分。
类似于 KMP 的 next 数组的思想,我们考虑在字典树上失配会怎么样:朴素的来说我们会返回到根重新来找,但是利用字典数上公共前缀的特性可以减少这些无用的计算量。
https://blog.aor.sd.cn/wp-content/uploads/2018/12/1149206-20171205083427159-776714463-1024x618.png
(图侵删)
那么考虑如何构造这个 fail 指针呢?
我们定义每个节点的 fail 指针的寻找方式为:沿着当前点的父亲的 fail 指针跳到一个点的儿子和这个节点代表的字母相同的点,则 fail 指针指向这个子节点。
形式化一下:设当前点是 $v$,则我们沿着 $fa_v$ 的 fail 指针一直跳到第一个点$t$ 满足 $t$ 的一个子节点和 $v$ 代表的字符相同,那么执行 v->fail = t->child

查找

查找就比较简单了吧 =-= 综合一下 KMP 和 Trie 树的查找即可。
按照这个字符串当前的数字在 Trie 树中搜索,一旦失配回溯到这个节点的 fail 指针指向的节点,并且继续往下找即可。

模板题 1

题目链接
题目描述:给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。
裸的 AC 自动机模板题,直接套板子就可以了。

模板题 2

题目链接
题目描述:有 $N$ 个由小写字母组成的模式串以及一个文本串 $T$。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 $T$ 中出现的次数最多。
这个题目实质上差不多,就是我们对于 Trie 树上的每一个单词终点记录的不再是一个计数器,而是对应单词的编号,遇到编号累加答案最后排个序输出就可以了。

总结

AC 自动机是一种简单的自动机,可以和 dp 等算法巧妙结合。我听说有人把莫比乌斯反演放在了这上面
但是注意千万不要把这种数据结构和某些评测软件的自动”AC”机混为一谈,当然我很仁慈的不给出自动”AC”机的代码以供大家警示大家不要用错名词$qwq$。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/347
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

AC 自动机学习笔记
定义 首先简要介绍一下 AC 自动机:Aho-Corasick automation,该算法在 1975 年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出 n 个单词,再给出一段包含m个字符…
扫描二维码继续阅读
2018-12-11
标签
近期评论