AC 自动机（ACAM）

· · 个人记录

前置芝士：trie（字典树）

题单

闲话

因为不会德文的这题来学的。

因为笔者也只能速通 ACAM，难免有错漏之处。希望各位大佬不吝赐教，蒟蒻再次拜谢。

引入

学习 AC 自动机的第一要义：它不能帮你自动 AC！

AC 自动机（英文名为 Aho-Corasick automaton，以下简称 ACAM），是一种多模式串匹配算法，它是由贝尔实验室的两位研究人员 Alfred V. Aho 和 Margaret J.Corasick 于 1975 年发明。

KMP 算法则是常用的单模式串匹配算法。无法高效解决在一段文本串中一次性匹配多个模式串的问题。

定义

简介

ACAM 是结合了 KMP 的失配指针和 trie 的树形结构的一种算法。俗称“KMP 上 trie”。但事实上和 KMP 区别不少。

建 ACAM 需要在 trie 上建边。一般称为“补 trie 图”（加边后就变成图了）。加的边是 fail 边，每个节点都有一条往外的 fail 边，令 trie 上从根节点到这个节点的字符串为 s，fail 边指向的是 trie 上出现过的 s 的最长后缀（不能是 s）所代表的节点，没有就指向根节点。

建 fail 边比较难以解释 其实是窝不会。这里丢几个比较详细的链接。

相信各位应该都会建 fail 边了（即建立 ACAM）。fail 边到底是干什么用的？

比如 trie 上有一个 S 节点（根节点到 S 节点所构成的字符串为 s）。我们从 S 节点一直跳 fail 边直到根节点，根节点到路径上所经过的每个点所构成的字符串是 trie 上所有 s 的后缀。

我们再讲一个东西叫 fail 树。

所有 fail 边单独看又构成一棵 fail 树。fail 树怎么建？只要把所有 fail 边反向连起来就建好了。它在我们需要多次暴力跳 fail 边时可以把它拎出来配合树上技巧来优化。

比如：统计串 s 在串 t 中的出现次数。我们先把 trie 上 t 的所有节点加一，那么答案就是以 S 节点为根的 fail 树的权值和。

解释一下：把 trie 上 t 的所有节点加一就是 t 的不同结尾都可能产生贡献。以 S 节点为根的 fail 树的所有节点又全是以 s 为后缀的串。这里比较抽象，可以画个图理解一下。

我们通过模板题来了解一下。

P3796 【模板】AC 自动机（加强版）

先把所有模式串建立一个 trie，然后建立 fail 边。

我们在 trie 上把每个字符串末尾打标记。然后把文本串放到 trie 上去遍历，对于每个被遍历到的点，我们都暴力跳 fail 直到根，如果遇到一次打标记的点就说明遇到一次，根据对应标记增加其出现次数。

虽然这题可以过，但是复杂度比较劣。是文本串乘模式串。代码。

考虑操作的本质：文本串每个点的贡献增加是从这个点到根的一条链。使用树上差分的思想最后对 fail 树一遍 dfs 即可。复杂度降至线性。代码。利用这种思想可以做二次加强版。

P5231 [JSOI2012] 玄武密码

建 trie 时把所有点的深度和父亲记录下来，把每个串的末尾记录下来。

把文本串所有点都暴力跳 fail 边，标记所有经过的点。

询问的时候从串的末尾往父亲找，第一个有标记的点的深度就是答案（有标记意味着出现过，第一个意味着深度最大）。

因为数据水所以过了。事实上，这种做法可以被字母全部相同的 10^7 的文本串和 100 的模式串卡成 \mathcal{O}(n |t|)。

其实加个简单的剪枝即可。如果这个点已经被打标记了，那么它上面的所有点肯定也被打标记了，就不用再跳 fail 边了。这样每个点最多被打一次标记，复杂度为 \mathcal{O}(n+m|t|)。代码。

CF547E Mike and Friends

题解

考虑 AC 自动机。

先把所有串的 trie 树建出来，再把 fail 树建出来。

题目求 s_{l \dots r} 的次数，拆成 s_{1 \dots l-1} 和 s_{1 \dots r} 两个询问。

像扫描线的思路把询问排序。考虑一个一个插入字符串。每个串会增加 trie 上经过的点的贡献。

询问就是 fail 树的子树权值和。

操作有：

可以使用 dfs 序配合树状数组求解。

由于字符串的总长度是有限制的，所以每个字符串暴力跳每个点复杂度是有保证的。

时间复杂度 \mathcal{O}((N +q)\log N),N=\sum |s| \le 2 \times 10^5，代码。

相关习题

参考资料