AC 自动机 - 算法与应用小结

标签：数据结构   序列   文本   父亲节   处理   head   单点   header   超过   

本文对 AC 自动机的算法以及基础应用略作总结。

定义

AC 自动机在 Trie 上构造失配指针

状态 \(u\) 的失配指针 \(fail\) 指向状态 \(v\)，即 \(v\) 是 \(u\) 在字典树所有状态集合中的最长后缀

转移边 \(trans\) 指向在当前对应串后续上一个字符能到达的状态

注意 \(trans\) 不仅仅是 Trie? 中的部分

KMP 的 next 数组对应 AC 自动机在单串时的特例

构造

设当前结点为 \(p\)，父节点为 \(f\)，且 \(f\) 通过字符 c 的转移指向 \(p\)

即 \(trie[f][c]=p\)

递推 fail[]

现在所有深度更小的结点的失配指针已经求出

若 \(trie[fail[f]][c]\) 存在，则令 \(fail[p]=trie[fail[f]][c]\)

否则，从 \(f\) 不断沿着失配指针向上跳，如果能找到一个点 \(t\) 使得 \(trie[t][c]\) 存在则令 \(fail[p]\) 等于 \(trie[t][c]\)，否则等于 \(root\)

当然，由于深度更小结点的失配指针已经求出，我们可以直接令 \(fail[p]=trie[fail[f]][c]\) 即可

转移边的补充

通常我们会补充另一类转移边，将字典树中不存在的转移链接到了失配指针的对应状态

设 \(S+c=S‘\)，若 \(S‘\) 不存在，我们让 \(trans[S][c] \to trans[fail[S]][c]\)

这样一来，当失配发生时，我们不需要沿着 \(fail\) 链狂跳，只需要接着走原本不存在的 \(trans\) 就能穿越到正确的位置了

应用

基础模式匹配

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

给定一堆模式串和一个文本串，问模式串们在文本串中各出现了多少次

设当前点为 \(p\)，每新进来一个文本串字符就沿着 \(trans\) 走，并沿着 \(fail\) 链往根走一趟，沿途所有结束点都 \(+1\) 即可

可以扩展到每个串的所有前缀出现多少次，基本没有区别

虽然可以通过本题，但这个方法在效率上有不足，下文中会给出改进

P3808 【模板】AC自动机（简单版）

只需要判断哪些模式串出现，我们可以在跳完每条 \(fail\) 边后就把这条边拆掉，因为每条 \(fail\) 边第一次走的时候才有可能对答案产生新的贡献

P5357 【模板】AC自动机（二次加强版）

题目与 P3796 相同，但对效率要求更高：给定一堆模式串和一个文本串，问模式串们在文本串中各出现了多少次

改变一下策略，不跳 \(fail\) 链了

先记录下匹配过程中每个结点被访问的次数

然后在 \(fail\) 树上搞子树和即可（某个节点实际的答案是它子树中所有节点被访问次数的和）

注意跑前缀和需要把树建出来跑，不能直接按照标号降序处理

非严格双倍经验题：[TJOI2013] 单词

ACAM x DFS/BFS

[POI2000] 病毒

给出 \(n\) 个 01 字符串，称为病毒串。问是否存在一个无限长的串使得其中不包含任何一个病毒串。

将所有病毒串插入自动机，末尾结点染黑，并沿着 fail 树下传（父黑子必黑）

找一个与根结点连通的白色环路即可

从根结点开始 DFS，所有点有三种状态：在栈中，未访问，已结束

碰到黑点直接设为已结束，否则继续下去，遍历其孩子，若未访问则访问，若在栈中则成功

[HNOI2006] 最短母串问题

给定 \(n \le 12\) 个字符串，要求找到一个最短的母串使得这 \(n\) 个字符串都是它的子串。如果有多个合法解则输出字典序最小的。每个字符串的长度不超过 \(50\)。

对 \(n\) 个字符串建立 AC 自动机，对于每个串的末尾结点，打上标记

建自动机的时候把标记下传一下

问题转化为找一条穿过所有标记的最短路径（还要字典序最小）

然后结合状压跑 BFS 即可，记录下每个点的来源，然后倒序输出

BFS 的时候先从小边走，以保证字典序

ACAM x DP

[HNOI2004] L语言

给定字典和没有标点的文章，求能够被识别的最长前缀。

显然不能贪心，设 \(f[i]\) 表示文本串前 \(i\) 个字符构成的前缀能否被识别，考虑主动转移，在 AC 自动机上每走到一个新位置，就沿着 fail 链把所有能转移的都转移了。

Wannafly Camp 2020 Day 2K 破忒头的匿名信

给定字典和文章，每个单词有一个代价，文章必须由选择的单词序列顺序相接而成，求写文章的最小代价

设 \(f[i]\) 表示写出 \(s[1..i]\) 的最小代价，考虑被动转移，每走一步后，沿着 fail 链往根跳，路途上经过所有的匹配点都用来更新依次答案

能保证复杂度的原因是，不同长度的单词串一定只有根号级别，而相同长度的在同一个状态的更新中至多出现一个

[JSOI2007] 文本生成器

给定 \(n\) 个单词和正整数 \(len\)，求有多少个不同的长度为 \(len\) 的串，至少包含一个给定的单词。

设 \(f[i][j]\) 表示长度为 \(i\)，当前处于 \(j\) 结点状态的方案数，沿着 \(trans\) 边主动转移即可

[USACO12JAN] Video Game Combo

给定 \(N\) 个模式串。一个母串的分数定义为能与模式串匹配的次数，可以与同一个模式串多次匹配。问一个长度为 \(K\) 的母串最多能获得多少分。\(N\leq 20,K \leq 1000\)

设 \(f[i][j]\) 表示长度为 \(i\)，当前处于 \(j\) 结点状态的最大得分，考虑主动转移，用 \(f[i][j]\) 去更新 \(f[i+1][ch[j][k]]\)

这里需要用到 \(val[p]\) 表示结点 \(p\) 到 \(root\) 的链上有多少个结尾标记，用树上前缀和预处理即可

ACAM x 数据结构

[COCI2015] Divljak

给定 \(n\) 个模式串 \(S_1,...,S_n\)，维护一个初始为空的字符串集合 \(T\)，有 \(q\) 个操作，每次向集合中添加一个字符串，或给定 \(x\) 询问集合中有多少个字符串包含 \(S_x\)。

考虑对 \(\{S_i\}\) 建立 ACAM，尝试对 ACAM 上的每个结点维护一个 \(ans[p]\) 表示有多少个 \(S\) 中的字符串能匹配到这个状态

那么每次新添加一个串，就扔上去跑，一个点发生匹配，则会对它（在 fail 树上）到根的链产生影响

但需要注意的是，由于这里问的是有多少个字符串包含 \(S_x\)，而不是总共匹配了多少次

因此我们每添加一个串时，需要修改的不是若干条到根的树链的和，而是它们的并

先考虑树链的和怎么做，直接树剖当然可以，但不妨转化为单点修改，子树查询，这样 DFS 序上建树状数组即可

再考虑树链的并，考虑容斥

若将这些待修改结点按照 DFS 序排序，树链的并等于树链的和减去所有相邻点 LCA 的父亲到根的树链，于是仍然可以按照上面的方法处理

[NOI2011] 阿狸的打字机

对一台打字机，除了可以正常打出小写字母（添加在当前缓存串的末尾），还有两个功能字符：P 表示打印当前缓存中的串，B 表示删去缓存末尾的一个字符。给定一个操作串。你需要回答 \(m\) 个询问，每个询问指定 \((x,y)\)，求第 \(x\) 个打印的字符串在第 \(y\) 个打印的字符串中出现了多少次。

按照操作串建 Trie，遇到 P 操作就将当前结点打上标记，遇到 B 操作就回溯到父亲节点

询问 \((x,y)\)，就是求 fail 树上以 \(x\) 为根的子树内，有多少个 \(y\) 沿着 Trie 树上的边走到根的路径上的结点

考虑离线，将 Trie DFS 一遍，维护一个桶，\(b[i]\) 表示当前所在点到根的链上是否有 \(i\) 这个点

将每个询问挂在 \(y\) 上，回答询问只需要在进入 \(y\) 点时，求桶中 \(x\) 点的子树和即可

于是桶需要按照 DFS 序做下标，并用树状数组维护

杂题

[USACO15FEB] Censoring

给定文章串 \(S\)，要从 \(S\) 中删去由 \(n\) 个单词构成的单词簿中的所有单词。每次找到最早出现的单词并且删除，重复操作到没有单词簿中的单词为止。输出最后的 \(S\)。

可以理解为每次碰到对应的单词就按若干下退格键

我们应当要记录每个时刻所在的结点来实现退格

不难想到用栈来维护，一个栈记录结点编号，一个栈记录输出串

遇到匹配的情况，就两个栈一起弹出长度次

AC 自动机 - 算法与应用小结

标签：数据结构   序列   文本   父亲节   处理   head   单点   header   超过   

原文地址：https://www.cnblogs.com/mollnn/p/13197243.html