AC自动机题目选讲

AC自动机复习：AC 自动机 - OI Wiki

先完成模板：luogu的

下面的所有例题代码我用的是ldytxdy这个账号提交，可以直接在cf上查看代码。

复习题

\(1.\)?CF1202E

枚举断点，设 \(\large s_i\)?? 和 \(\large rs_i\) ??分别表示以\(i\)??为结尾的前缀/后缀的匹配个数，答案为

\[\large \sum_{i=2}^{n}s_i \times rs_{i-1} \]

\(\large s_i\) ?和 \(\large rs_i\) ?可以通过分别建正反串AC自动机求出。

AC自动机上dp

\(2\)?.CF696D

设 \(\large f_{i,j}\)?? 为答案串匹配到前\(i\)??位，在AC自动机的 \(\large j\) ??节点的最大值

\(\large val(x)\) ?表示把原串权值记在\(x\)?号点

\[\large f_{0,0} = 1\\ \large f_{i,j} + val(tr_{j,k})\to f_{i+1,tr_{j,k}} \]

矩乘优化即可。

\(3\)?.SDOI2014 数数

设 \(\large \ f_{pos,p}\)??? 表示答案数位在 \(\large pos\)??? 且AC自动机节点在 \(\large p\)??? 的方案数

设 \(\large op(x)\)?? 为 \(x\)?? 是否为结束节点

\[\large f_{0,0}=1\\ \large f_{i,j} \to f_{i+1,tr_{j,k}}(op(tr_{j,k})=false) \]

用数位dp实现这个过程

练一练：CF86C

简单数据结构+AC自动机

\(5.\)????NOI2011 阿狸的打字机

考虑题目中加减字符的实际意义就是在trie树上dfs，所以我们把询问离线到每个结束点上做一遍dfs

我们建出fail树，考虑AC自动机跳fail树的匹配过程，需要实现的操作就是单点加和查子树和

记下fail树的dfn序后树状数组，记得dfs回溯的时候撤销贡献。

\(6\)????.CF547E

考虑离线，每个询问可以拆成前缀和相减的形式，用vector记录每个位置的询问

每扫到一个字符串，在fail树上把这个字符串代表的所有节点权值 \(\large +1\)?

答案就是查 \(\large s_k\)? 在fail树上结束点的子树和。套用上题做法即可。

\(7.\)??CF1437G

根据上两题的经验很容易做出来，需要实现单点加和点到根的总权值，树剖维护。

练一练：CF163E

好题

\(8\)?.CF710F

CF163E的在线版本

AC自动机的删除是很困难的

建出两个AC自动机，分别塞入删除和增加的串，答案就是在两个AC自动机上分别做一遍匹配然后相减。

考虑二进制分组，每组建一个AC自动机，加入时往前合并，具体实现与线段树合并类似。

显然每个串至多合并 \(\large log_2n\)?? 次，所以复杂度是 \(\large Slogn\)? ?, \(\large S\)?? 表示总串长。

\(9.\)???CF587F

因为我们做了CF547E，所以可以很容易看出答案就是：

将 \(\large l...r\)?? 中所有\(\large s_i\)??的结束点子树每个点 \(\large +1\)? ?后 \(\large s_k\)?? 代表字符所有节点的总权值。

这样就不能像之前的题用树状数组的单点加实现了，考虑离线根号分治。

设 \(\large len_i\)?? ???表示 \(\large s_i\)????? 的长度，设所有 \(\large s_i\)????? 总长度为 \(\large M\)?? ???，并且设一个阈值 \(\large L\) ?????.

\(\large I.\)\(\large len_i \leqslant L\)??

依次扫过 \(n\)? 个串，每扫到一个串用树状数组实现子树加，查的时候暴力单点查一个字符串的所有点。

复杂度分析：子树加是 $\large O(nlog_2M) $???的，查询是 \(\large O(QLlog_2M)\)? ??的

\(\large II.\)\(\large len_i>L\)

显然这样的 \(\large s_i\)?? 个数是不超过 \(\large \frac M L\) ??的

还是依次扫过 \(\large n\)?? 个串，我们对于每个 \(\large s_i\)?? 的节点做一次单点加，查就是一个子树和。

这个可以不用数据结构，暴力做就好了。

复杂度分析：单点加： \(\large O(\frac {M^2} L)\)???? ，因为要把询问排序所以询问的复杂度是 \(\large O(Qlog_2Q)\) ????的

利用均值不等式设 \(\large \frac {M^2} L = QLlog_2M\)???? 解得 \(\large L=\frac {M} {\sqrt {qlog_2M}}\)????

所以总复杂度是 \(\large O(nlog_2M+Qlog_2Q+M\sqrt {Qlog_2M})\)?

\(10.\)???CF1483F

显然 \(\large (i,j)\)?????合法当且 \(\large s_j\)?? ???在 \(\large s_i\)????? 中不被任意一个 \(\large s_k\) ?????覆盖

我们枚举每个字符串作为 \(\large i\)???，从后往前枚举 \(\large s_i\)???的每个位置 \(\large p\)???

我们需要寻找出以 \(\large p\)??? ??结尾的最长子串 \(\large S\)????? 使得 \(\large S \in s_{1...n}\)?????，设 \(\large S=s_x\)?????

设 \(\large S\)????? 的左端点为 \(\large L\)?????，设 \(\large pre\)? ????为之前扫过的最大的 \(\large L\)?????

如果 \(\large pre>L\)??? ?那么这就是 \(\large s_x\)?? ??不被包含的一次，此时 \(\large cnt_{s_x}+1\)????，并用 \(\large L\)? ???更新 \(\large pre\)????

最后答案加上有多少个 \(\large cnt_i\)? ?满足 \(\large cnt_i=\)?? 总出现个数

经典工业题

luoguP5599 XR-4 文本编辑器

模板

最后附上我的板子，是这个的AC代码。

#include 
using namespace std;
const int N=1e6+5;
int n;char s[N];
int tr[N][27],fail[N],End[N],tot;
queueq;
void ins(char *s){
	int p=0,m=strlen(s);
	for(int i=0;i