AC自动机学习笔记 | ouuan的博客

[ouuan]

https://ouuan.github.io/AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

AC 自动机其实我去年就学过了，但当时大约只是会敲模板而已..现在几乎全忘光了。于是复习一下，顺便（较为本质地）讲解一下。

[EndSaH]

实际上这应该不是 AC 自动机，可以参考 wiki 百科，这种应该叫做 Trie 图，AC 自动机是优化了空间后的结果。

在每一步中，算法先查找当前节点的“孩子节点”，如果没有找到匹配，查找它的后缀节点(suffix)的孩子，如果仍然没有，接着查找后缀节点的后缀节点的孩子, 如此循环, 直到根结点，如果到达根节点仍没有找到匹配则结束。

（引自 wiki 百科）

虽然看起来比 Trie 图劣，但是时间复杂度均摊下来貌似还是对的，而且在字符集极大（比如汉字）的情况下有效地节省了空间。 看构建代码也看的出来，Trie 图的空间是要开满的，AC 自动机作为优化版是动态开的。

[EndSaH]

构造时的主要区别在这里：

 else tr[u][i] = tr[fail[u]][i];

AC 自动机的构造里没有这一步。

[ouuan]

@EndSaH 实际上这应该不是 AC 自动机，可以参考 wiki 百科，这种应该叫做 Trie 图，AC 自动机是优化了空间后的结果。

在每一步中，算法先查找当前节点的“孩子节点”，如果没有找到匹配，查找它的后缀节点(suffix)的孩子，如果仍然没有，接着查找后缀节点的后缀节点的孩子, 如此循环, 直到根结点，如果到达根节点仍没有找到匹配则结束。

（引自 wiki 百科）

虽然看起来比 Trie 图劣，但是时间复杂度均摊下来貌似还是对的，而且在字符集极大（比如汉字）的情况下有效地节省了空间。 看构建代码也看的出来，Trie 图的空间是要开满的，AC 自动机作为优化版是动态开的。

我认为您说的这两种东西在“自动机”这个概念上是一致的 —— 字符集、状态集合、初始状态、接受状态、转移函数一致。

这只是代码实现上的问题，我认为是基于 AC 自动机的两种不同的多模匹配算法，你说它们其中之一是 AC 自动机而另一者不是，我找不到原因，还请说明。

[ouuan]

看了下论文，两种方式都介绍了，而且有“不建 Trie 图”的复杂度证明，我待会儿可能加进正文。

只不过我依然不同意“Trie 图”不是 AC 自动机。

[EndSaH]

@ouuan 我同意你的观点。由于没有学习自动机相关概念，所以我之前认为 AC 自动机是否建补边对应的应该是两种数据结构。

顺便问下，如果要正式的区分建/不建补边（我之前叫不建的叫"Trie 图"，我觉得这个描述很形象）的话，应该分别叫做什么名字？

[ouuan]

@EndSaH @ouuan 我同意你的观点。由于没有学习自动机相关概念，所以我之前认为 AC 自动机是否建补边对应的应该是两种数据结构。

顺便问下，如果要正式的区分建/不建补边（我之前叫不建的叫"Trie 图"，我觉得这个描述很形象）的话，应该分别叫做什么名字？

我不清楚应该怎么区分，如果要我区分的话我会分别称作“将转移函数存下来的 AC 自动机” / “显式建出所有转移边的 AC 自动机”和“递归计算转移函数的 AC 自动机” / "每次跳 fail 的 AC 自动机"。