AC 自动机 学习笔记

## 什么是 AC 自动机 AC 自动机（Aho-Corasick automaton，*abbr.* ACAM），诞生于贝尔实验室。 AC 自动机是一种**多模匹配算法**，就是解决 **多个模式串** 匹配 单个/多个 文本串用的。 之后的复杂度分析均用 $s_i$ 代表模式串，$t_i$ 代表文本串。 ## AC 自动机的主过程 以[P3808 【模板】AC自动机（简单版）](https://www.luogu.com.cn/problem/P3808)为例。 看到有很多个模式串，自然想到建一棵 Trie 树，那么建了 Trie 树之后我们就从头开始尽可能地向下走。 要是往下匹配走到头了怎么办呢？我们考虑借用一个 KMP 的思想，从当前节点跳到它的**最长的在 Trie 中的真后缀**，这样就可以继续匹配了。 具体地，我们对每个结点定义一个 $\text{fail}$ 指针，指到当前结点最长的在 Trie 中的真后缀。 那么怎么求出这个 $\text{fail}$ 指针呢？只需要和 KMP 一样不停地向前跳就可以了，这样就在 $\mathcal O(\sum|s_i|)$ 的时间内完成了建树。 具体实现时，由于 $\text{fail}$ 的长度一定小于原串的长度，我们可以用一个 BFS 的过程完成。 Code： ```c++ void build() { fo(i,0,25) if(trie[0][i]!=0) q.push(trie[0][i]); while(q.size()) { int x=q.front().x; q.pop(); fo(i,0,25) { if(trie[x][i]!=0) { fail[trie[x][i]] = trie[fail[x]][i]; q.push(trie[x][i]); } else { trie[x][i] = trie[fail[x]][i]; } } } } ``` 可以发现，我们把 $\text{fail}$ 指针直接并在了原先的 Trie 中，这样形成的一个数据结构叫作**字典图**。 - **性质：字典图中的树边和非树边各自构成一张 DAG。** > 证明：树边显然是 DAG，而每条非树边总是从一个字符串连向它的一个**真后缀**。 > > 这样随便反证一下就证完了。 - **注意：整张字典图不一定是 DAG！** 回到这道题，这道题统计答案时可以直接暴力跳 $\text{fail}$，跳到某个结点就打一个 $-1$ 的 tag，就做完了。 可以发现，复杂度是 $\mathcal O(\sum|s_i|+n|\Sigma|+|T|)$，其中 $|\Sigma|$ 代表字符集的大小。 OI - Wiki 中说如果不建字典图并且避免跳到空结点就可以去掉 $n|\Sigma|$，不过貌似没啥用。 Code： ```c++ #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define il inline const int N=5000010; int n, len; char s[N]; int cnt[N], trie[N][26], tot, fail[N]; void insert() { len=strlen(s+1); int p=0; fo(i,1,len) { if(trie[p][s[i]-'a']==0) trie[p][s[i]-'a']=(++tot); p = trie[p][s[i]-'a']; } cnt[p]++; } queue<int> q; void build() { fo(i,0,25) if(trie[0][i]!=0) q.push(trie[0][i]); while(q.size()) { int x=q.front(); q.pop(); fo(i,0,25) { if(trie[x][i]!=0) { fail[trie[x][i]] = trie[fail[x]][i]; q.push(trie[x][i]); } else { trie[x][i] = trie[fail[x]][i]; } } } } int query() { int p=0, ans=0; len=strlen(s+1); fo(i,1,len) { p = trie[p][s[i]-'a']; for(int j=p; j&&cnt[j]!=-1; j=fail[j]) ans+=cnt[j], cnt[j]=-1; } return ans; } int main() { cin>>n; fo(i,1,n) { scanf("%s",s+1); insert(); } build(); scanf("%s",s+1); printf("%d\n",query()); return 0; } ``` [Record](https://www.luogu.com.cn/record/61104247) ### 例题 - [P3966 [TJOI2013]单词](https://www.luogu.com.cn/problem/P3966) 尝试在 ACAM 上匹配自己。 你发现只要建出 ACAM，然后尝试把每个字符串作为文本串做一遍。 当然也可以有一种更精妙的做法，就是统计每个结点在几个字符串中出现过，这样每个结点的权值就是其子树内值的和。 代码懒得打。 - [P3121 [USACO15FEB]Censoring G](https://www.luogu.com.cn/problem/P3121) 你发现你好像不太会做。 后来你发现不会出现一个单词是另一个单词子串的情况，于是你就秒了。 具体地，这个性质保证了**如果两个字符串中的一个开始位置小，那么它的结束位置也小**。 这样就可以在 ACAM 上乱搞了，具体实现时可以考虑维护一个栈，然后记录每个位置对应的结点。 [Code](https://www.luogu.com.cn/record/61196473) ## Fail 树 - [P5357 【模板】AC自动机（二次加强版）](https://www.luogu.com.cn/problem/P5357) 这题严格不弱于[P3796 【模板】AC自动机（加强版）](https://www.luogu.com.cn/problem/P3796)。 先说 P3796 这个 Easy version。这道题中，我们建好 ACAM 后，直接暴力往上跳 $\text{fail}$ 就能过。 ```c++ void query() { int p=0, len=strlen(s+1); fo(i,1,len) { p = trie[p][s[i]-'a']; for(int j=p; j; j=fail[j]) if(id[j]!=-1) cnt[id[j]]++; } } ``` [Code](https://www.luogu.com.cn/record/61122613) 但是我们发现查询的复杂度非常不行。 比如我们取 $s=\{\texttt{a},\texttt{aa},\texttt{aaa},\texttt{aaa},\cdots\}$，然后 $t=\mathtt{aaa\cdots a}$，模拟一下过程发现这个查询被我们卡到了平方级别。 P5357 卡掉了这一暴力，那么怎么做呢？ 我们发现，所有的贡献都是在 $\text{fail}$ 指针上完成的，而所有 $\text{fail}$ 指针连的边形成一个 DAG，这样我们就可以考虑拓扑排序。 但是，有一种更为通用、简洁的打法，那就是 **Fail 树**。 具体地，我们把除了根节点以外所有点的 Fail 指针倒着连。 这样，由于每个点只会有一个 Fail 指针，因此这样形成的图是**以 $0$ 为根的树**。 - **性质：一个字符串的所有后缀就是这个结点的所有祖先**。 > 证明：显然。 这样就可以把字符串题转化成一个图论问题了。 比如在这道题中就等价于求出每个结点的子树中的贡献，直接一遍 DFS 即可。 [Code](https://www.luogu.com.cn/record/61165943) - [P2414 [NOI2011] 阿狸的打字机](https://www.luogu.com.cn/problem/P2414) 一道好题。我们依照题意建出 ACAM，这样得到一棵树。 然后我们发现：字符串 $x$ 在 $y$ 中的出现几次，$y$ 就有恰好几个前缀在 $\text{fail}$ 树中是 $x$ 的一个后代。 显然要离线。我刚开始想要离线 $x$ 一维，然后得到了一个 DSU + BIT + ACAM 上树剖的巨大多 $\mathcal O(n\log^3 n)$ 做法，觉得我是煞笔。 然后考虑离线 $y$ 一维，然后你就会了复杂度 $\mathcal O(n\log n)$ 的做法。 具体地，我们 DFS 整棵 $\text{fail}$ 树，然后记录每个点的 DFS 序。再 DFS 一遍 Trie，然后用和树剖类似的做法统计贡献。 [Code](https://www.luogu.com.cn/record/61444492) **注意：这种数子串一般都考虑 ACAM，是从子串处计算子树贡献。** - [CF163E e-Government](https://www.luogu.com.cn/problem/CF163E)：建出 ACAM，在 $\text{fail}$ 树上子树加，单点查。 ## AC 自动机配合 DP 这种问题的特征是**得到的字符串中 能/不能 出现模式串中的任何一个**，一般复杂度都是 **ACAM 结点数 * 字符串长度** 的。 - [P3041 [USACO12JAN]Video Game G](https://www.luogu.com.cn/problem/P3041) 看到这个极小的数据范围，显然 DP。 我们对每个结点，预处理出有 $cnt_i$ 个字符串是它的后缀，然后设 $dp_{i,j}$ 为长度为 $i$，以结点 $j$ 结尾的最大值。 有转移：$dp_{i,x}=dp_{i-1,fa_x}+cnt_i$。然后用 $dp_{i,x}$ 去更新 $dp_{i,fail(x)}$。这个 DP 过程可以用树上 DP 实现。 [Code](https://www.luogu.com.cn/record/61174483) - [P4052 [JSOI2007]文本生成器](https://www.luogu.com.cn/problem/P4052) 简单容斥。[Code](https://www.luogu.com.cn/record/61207948) - [P3311 [SDOI2014] 数数](https://www.luogu.com.cn/problem/P3311)： 就是在上面那题基础上加了一个数位 DP。[Code](https://www.luogu.com.cn/record/61427651) ## 例题 有一个比较 nb 的[题单](https://www.luogu.com.cn/training/60465)，挑了几道题出来。 - [P2444 [POI2000]病毒](https://www.luogu.com.cn/problem/P2444) 我们先建出一棵 ACAM，我们发现结点不合法，当且仅当它在 $\text{fail}$ 树中没有被打过 tag 的祖先。 之后我们发现存在一种无穷串合法，当且仅当 ACAM 中存在一个合法环，那么我们 DFS 这个 ACAM，找环就可以了。 直接交过不去 hack：`1 0`，解决方法可以在刚开始把根节点的左右儿子建好。 [Code](https://www.luogu.com.cn/record/64085159) - [P2336 [SCOI2012]喵星球上的点名](https://www.luogu.com.cn/problem/P2336) 我们考虑对点名串建 ACAM，然后树上统计。 到如果直接建字典图，复杂度会爆炸，那么我们可以开 `STL map`，建图时不建出整张字典图，在匹配失败时直接跳 $\text{fail}$ 即可。 这样我们把题目转化成这样一个东西： > 给一棵树，$Q$ 次询问，每次询问给出一个点集 $S$，求 $S$ 中所有点到根的路径中包含的点的并集大小。 然后我就不会简单做法了。。。硬刚的话会一个倍增+树状数组的 2log 做法，可能过不了。 然后就看题解，发现了一种 nb 做法，就是对这个点集**按 DFS 序排序然后相邻项 LCA**。 [Code](https://www.luogu.com.cn/record/61596667) - [P5840 [COCI2015]Divljak](https://www.luogu.com.cn/problem/P5840)：差不多相当于前面那道题的逆运算。[Code](https://www.luogu.com.cn/record/61893277) - [P7582 「RdOI R2」风雨(rain)](https://www.luogu.com.cn/problem/P7582) 数据结构题。无论题怎么改，这种区间问题一定要想到线段树、分块！！！ 然后如果我们考虑建线段树，空间复杂度会爆炸，所以我们考虑分块。 回忆一下区间加、区间推平的维护，就是在每个块上维护加法、推平 tag，然后散块修改时直接下传。 调了快一天[Code](https://www.luogu.com.cn/record/61721976) - [CF1483F Exam](https://www.luogu.com.cn/problem/CF1483F) 还是考虑建出 ACAM，然后我们发现 $s_i$ 和 $s_j$ 符合题意当且仅当 $s_j$ 不在 $s_i$ 中有过被别的串包含的出现。 倒序枚举 $s_j$ 的右端点在 $s_i$ 中的出现，如果前一次合法的出现没有包含这一次就把它加上。 注意：这里如果直接 `ans++` 是错的，因为它可能在后面被覆盖。 因此我们需要检查每个出现过的 $j$ 的出现次数是否等于它不被覆盖的出现次数。 [Code](https://www.luogu.com.cn/record/65462279)