AC 自动机总结

AC 自动机总结

tony102

2021 年 08 月 04 日

782 次浏览

暂无评论

1304字数

总结

这玩意儿听起来牛逼哄哄的，毕竟一个 AC 一个自动机一般没接触过以为这是 `fun.cpp` 大法（@FlashHu）或者自动 AC 机。那么应该先总结一下什么叫做 AC 自动机。

## AC 自动机用途

AC自动机实际上是对 trie 树进行一些处理，使来处理的匹配串能在失配的情况下，迅速跳到最能匹配的位置，即“所有模式串的前缀中匹配当前状态的最长后缀。”

同时，fail数组则可以维护当前状态的最长的为 trie 节点的后缀，通过fail树的操作还可以处理所有为 trie 节点的后缀。

可以认为AC自动机是一个在线算法，能将我手上的一个字符串拆成一个个字符，每次单独加入（转移），它能尽可能的匹配到最长的包含这个字符的一串。

但有时可能匹配过了头，我们无法判断这最长的一串中有没有包含模板串，也就是带有结束标记的状态，这时候就需要fail树上找它的祖先，有没有这种状态。

再考虑一下为什么每次加入一个字符，然后就要处理一次。可以这么想，AC自动机是把一个字符串的所有子串先拆成 $n$ 个前缀，再对每个前缀找到在在AC自动机里出现的最长后缀，这时候这一段都可能是模式串。

所以我们再在fail树上按长度递减查找（每次向上跳一次可以想象成减掉了前面一段）

## 构建 AC 自动机

有人说 AC 自动机是树上的 KMP

下面来写一下步骤

- 把所有的模式串插到 trie 树上去
- BFS 处理 trie 的深度（串的长度）
- 设当前状态是 $p$, 我们从小到大枚举字典中的每一个字符，如果有在 trie 树的边（$t_{p,ch}$），就更新 $fail_{t_{p,ch}}$，否则则修改非树边 $t_{fail_p, ch}$

那最重要的是理解第三个步骤, 我觉得最好理解和记忆的方式就是一个串加上一个字符的最长真后缀就是这个串的最长真后缀加上这个字符。

## FSA：有限状态自动机

有一些文章上面介绍这玩意儿神乎其神的，其实我认为只有一些东西是我们需要知道的。

首先自动机是说具有离散输入和输出的系统的一种数学模型，有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。（例如 trie图）

还有一些特点我认为了解了对后面的内容更好：

1. 系统具有有限个状态，不同的状态代表不同的意义。
2. 系统处理的所有字符串都是这个字母表上的字符串。
3. 在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。
4. 有一个状态，它是系统的开始状态。

那么这些东西给我们对后面理解 AC 自动机的启发就是：**AC 自动机上的每一个节点都对应表示一个状态，若输入一个字符串在AC自动机上有匹配就一定有一个状态与之唯一对应。**

理解这句话很有帮助我们做一些在 AC自动机上转移 DP 的题目。

## 运用

可能会写一些题解，到时候在更吧

最后修改：2021 年 09 月 07 日