AC 自动机小记

题目

P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands

前后缀信息考虑放到字典树上去，则建出两棵字典树后，找到前缀字典树的一个节点的子树内的结尾节点与后缀字典树的一个节点的子树内的结尾节点的交集，显然可以转化为两段连续的 dfn 值，于是离线二维数点即可

P2414 [NOI2011] 阿狸的打字机

首先题目中的操作明显放到字典树上比较好维护，删除时回到父亲节点即可

然后查询操作表面上是单模匹配，但是多次查询且没有字符串总长度的限制，于是考虑在 ACAM 的失配树上做这件事

我们记 \(ed_i\) 表示第 \(i\) 个字符串在字典树上以哪个节点结尾，那么相当于查询失配树上的字数和，树状数组轻松维护

但是匹配串的总长度没有限制，我们发现这样一个性质：匹配串一定在字典树上出现过，也就是我们匹配的时候，走过的点连起来是从根出发的一条链，于是考虑离线，然后去 dfs 整棵树，每次进入一个节点加上他的贡献，离开的时候减去他的贡献，这样贡献就为一条链，可以处理查询

P14363 [CSP-S 2025] 谐音替换

考虑怎样的替换合法，设被替换的区间为 \([l,r]\)，则 \(l,r\) 分别都在 \(t1,t2\) 的最长公共前后缀里

此类问题比较像多模匹配，考虑上 ACAM，但是两个字符串实在不好维护，考虑转化成一个，并且能够去匹配

首先，要保证 \(s1,s2\) 里含有 \(t1,t2\) 不是公共前后缀的一部分，我们需要把这一部分区分开，如果直接把 \(s1,s2\) 中非最长公共前缀后缀的字串拼成一段，有可能长度不等但匹配上，此时考虑在前后各加一个特殊字符 #，这样就保证这部分的匹配

然后是 \(s1,s2\) 中可以拥有的 \(t1,t2\) 公共前缀的后缀，公共后缀的前缀部分，我们可以直接把 \(s1,s2\) 的最长前后缀拼在前后面，这样查询就不重不漏

形式话地：将一个变换 \(s1 \rightarrow s2\) 表示为 \(ABC \rightarrow ADC\)，其中 \(A,C\) 是最长公共前后缀，那么将其转换为 \(A\#BD\#C\)

特别注意 \(s1 = s2\) 的情况，特殊处理一下即可

P3121 [USACO15FEB] Censoring G

直接建 ACAM，每次在失配树上根到 \(u\) 链上找一个被标记过结尾的节点，删除这个节点所代表的字符串，注意到 “列表中的单词不会出现一个单词是另一个单词子串的情况”，所以这个点是唯一的。可以用栈维护，然后将 \(u\) 跳到原来的位置（这个删除的字符串的前一个字符的位置）

P2444 [POI 2000] 病毒

直接做过于复杂的，看到一个字符串中不出现多个字符串，容易想到 ACAM，于是考虑长度无限这个条件，相当于在 ACAM 匹配的时候走进环里，且不能匹配到任何一个模式串，也就是 fail 树上的一条链都没有结尾标记，这个预处理一下，保留合法的点跑 topo 就行了

P2292 [HNOI2004] L 语言

首先对模式串建 ACAM，那么 \(dp_i\) 表示前缀 \(i\) 是否能匹配，转移时枚举 \(fail\) 树上的点，如果这个点有结尾标记，那么用之前 dp 值更新

这样卡不过去，观察到 \(n,|S_i| \le 20\)，考虑状态压缩，设当前到 \(i\)，首先我们只关心 \([i-20,i-1]\) 的 dp 值，其次我们跳 \(fail\) 时只关心有结尾标记的点所代表的字符串的长度，于是弄出两个状态整数，通过 \(&\) 运算判断 \(dp_i\) 为 \(0/1\)

P3311 [SDOI2014] 数数

ACAM 上 DP 的经典题目

首先用 ACAM 组织所有模式串，然后考虑数位 dp，则我们需要知道一个信息：从自动机的 \(u\) 节点开始，跳 \(i\) 步，得到的合法字符串方案，注意还要加一位表示考不考虑前导 \(0\)，这个可以以 \(i\) 为阶段，在 ACAM 上求出

U636040 搬题1

首先建出 ACAM，每次加入一个文本串我们就计算它对模式串的贡献，于是转变为 fail 树上若干条链的并执行 \(+1\) 操作

这个不太好维护，有一种暴力的方法是用树剖搞出所有连续区间，再找出这些区间的并，数据结构维护，这样是双 \(\log\)，难以通过

我们手玩几组样例，发现很多链上重复计算的数值都相同。考虑先加上链的贡献，再减去重复的。对于一个节点 \(u\) 而言，它被重复算的次数 = 链的端点在它子树内的数量减 1，考虑将所有节点按 dfs 序排序使得子树内的点连续

所有连续区间的 lca 最多 \(k-1\) 种，且均属于相邻点的 lca 的一个，于是我们在根到相邻点 lca 的链上都做减一操作，这样就可以。

因为对于任意点 \(u\)，它子树内的链端点排完序后连续，且它们两两相邻的 lca 都在其子树内，所以最终贡献正确