AC自动机_杂项

8.2 专题：AC自动机

今日警钟：a[read()][read()]会死。

好好好。

一年前就 AC 了三道 ACAM 板子，然后全忘了。

本来寻思着重拾，但又不知道摆到哪里去了。

还好南外帮我重拾了哈哈哈哈哈。

发现这里效率真的高，一天差不多就学会一个新算法。

自动机的本质是一个状态加一个字符到达一个新状态，所以每个串在 ACAM 上都有自己的节点。

找这个节点是在 ACAM，或者叫 Trie 图上跑，其实就是 Trie 树跳不动了就跳 fail，然后接着跳 Trie。

$\text{Fail}$ 树的定义是每个前缀的父亲是最长的为其后缀的（自己串或其他串的）前缀。

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

交了 $7$ 发才过。

倒是试出了不少写这个板子的写法。

最后发现是字符串快读写错了。

while(c<'A'&&c>'Z')。

板子：

/*首先建Trie，根节点0*/
void buildf() {
    queue<int,list<int>> q;
    F(i,0,25) {
        int id=nxt[0][i];
        if(id) add(0,id),q.push(id); 
    } while(!q.empty()) {
        int x=q.front();q.pop();
        F(i,0,25) {
            int &id=nxt[x][i],&idf=nxt[fa[x]][i];
            if(id) add(idf,id),q.push(id);
            else id=idf;
        }
    }
}

简单说说这题的各种在板子基础上的写法。

一种写法是把文本串在 ACAM 上跑的所有结点在 fail 树上到根的链的并 +1。

这个各种实现都行，可以直接暴力跳fa，遇到加过的节点就停。

另一种写法是直接硬加，然后做树上前缀和，最后查每个模式串的权值是否 $\geq1$。

（这种写法可以直接查询每个模式串（可重叠）出现的次数。）

T2 P4052 [JSOI2007] 文本生成器

下面是 DP 时间！

（以下使用 $v$ 或 $nxt_{x,c}$ 来表示 $x$ 号节点在Trie上走一步 $c$ 边到达的儿子，若与 $c$ 关系不大则省略为 $v$。）

之前一直不是很会自动机上 DP 这种玩意。

其实真的很套路，就是把状态的某一维设为自动机上的节点。

自动机上一个节点转移到另一个节点的本质就是加了个字符，那我们的 DP 状态和转移也要从“往当前串后面加字符”来考虑。

细化到这个题呢？

首先出现至少一次不好求，我们求一次也没出现的。

然后就相当于每次在当前串后面增加一个字符，不能出现敏感串。

发现“不能出现敏感串”的限制相当于在 ACAM 上不能走到某些节点。

设 $f_{i,j}$ 为从空串开始加了 $i$ 个字符，跑到了自动机上的 $j$ 节点，方案数。

$$\forall v\text{ is safe},f_{i+1,v}\xleftarrow+ f_{i,j}$$

初始 $f_{0,0}=1,f_{\text{others}}=0$。

那什么样的节点包含敏感串，不能走到呢？

包含一个串相当于在fail树上是其后代。

所以只要每个点的祖先中有敏感节点，该点就为敏感节点。

其实不需要额外写个dfs来做这件事情，构建 ACAM 的过程相当于bfs一遍fail树（也可以理解为bfs一遍Trie，二者bfs序相等。），可以直接vis[id]|=vis[idf]。

（张老师：AC 自动机上 DP 就只有两行重要（即把串插入Trie时做的操作与构建fail树时做的操作，对应本题就是分别为vis[now]=1和vis[id]|=vis[idf]）。）

T3 P3041 [USACO12JAN] Video Game G

DP 题怎么写暴力柿子？

直接把所有维度包含进去，大力设状态大力转移。

这个题跟上题差不多是一模一样的，只是要把那两行改为sum[now]=1和sum[id]+=sum[idf]。

设 $f_{i,j}$ 表示长度 $i$，走到了 $j$ 这个自动机节点，最大获得分数。

$$f_{i+1,v}\xleftarrow\max f_{i,j}+sum_{v}$$

初始 $f_{0,0}=0,f_{\text{others}}=-\infty$

有了上一题基础就比较套路了。

T4 P2322 [HNOI2006] 最短母串问题

场上竟然没有第一眼就秒掉。

还是没有太熟练呢。

$n\leq 12$，直接压起来。

然后就一眼了。

首先处理出第 $i$ 个点包含 $T_i$ 集合的模式串。

设 $f_{S,i,j}$ 表示选了 $S$ 中的串，长度 $i$，节点 $j$，能否可行。

$$f_{S\cup T_{v},i+1,v}\xleftarrow{\text{OR}}f_{S,i,j}$$

由于一个状态如果已经是 $1$ 就不需要接着更新该状态了，可以直接广搜，每次先枚举最小的一条边走，这样搜到的时候就保证长度最短且字典序最小，直接记录前驱倒回来即可。

（前驱下标是二维的，可以直接记录一个bfs序。）

T5 P4045 [JSOI2009] 密码

如果只看第一问，似乎与上一题没什么区别。

那就先解决第一问。

设 $f_{S,i,j}$ 表示选了 $S$ 中的串，长度 $i$，节点 $j$，方案数。

$$f_{S\cup T_{v},i+1,v}\xleftarrow{+}f_{S,i,j}$$

这题是全部计数就不推荐写bfs了，直接枚举即可。

那么如何处理输出方案呢？

观察 $42$ 这个数，是不是有点过小了？

假如有一个位置可以 $26$ 个字母随便选，那把原串调整一定有两个位置可以分别随便选，那就 $52$ 种情况了。

所以字母一定是原串出现过的。

（这个好像没用到，但是有用的结论。）

可以从终态往前搜，不过我更推荐从前往后搜，跑到一个就输出一个。

状态就是 dp 的状态。

bool dfs(int x,int y,int z) {
    if(vis[x][y][z]) return ok[x][y][z];
    vis[x][y][z]=1;
    if(x==l) return ok[x][y][z]=(z==(1<<n)-1);
    bool res=0;F(l,0,25) res|=dfs(x+1,nxt[y][l],z|val[nxt[y][l]]);
    return ok[x][y][z]=res;
} char tmp[L];
void out(int x,int y,int z) {
    if(!ok[x][y][z]) return;
    if(x==l&&z==(1<<n)-1) {
        F(i,1,l) putchar(tmp[i]+'a');
        putchar('\n');
    } F(l,0,25) tmp[x+1]=l,out(x+1,nxt[y][l],z|val[nxt[y][l]]);
}

（不能将二者压成一个dfs，因为前一个dfs有可能递归到不合法状态内死循环，必须用记忆化，而记忆化会在合法状态中漏情况，所以需要再来一个只在合法状态中递归的非记忆化输出。）

T6 P3193 [HNOI2008] GT考试

比较玄幻的一集。

这个题就一个串，并不需要用 ACAM，直接 KMP 就可以。

（普通暴力跳nxt也是 $O(n)$ 的，不过也可以学习 ACAM 的写法来路径压缩减少常数。）

设长度为 $n$ 的那个串为 $s$，长度为 $m$ 的为 $t$。

设 $f_{i,j}$ 表示 $s$ 匹配到 $i$，$t$ 匹配到 $j$ 的方案数，转移就是枚举下一位选什么看能不能匹配上，由于前面已经匹配的部分我们不想重新跑一遍，可以在 KMP 上跑。

答案即为 $\sum_{i<m} f_{n,i}$。

但 $n\leq 10^9$，$m$ 只有 $20$，有一个大胆的想法。

观察发现对于 $f_i$，里面的一个长为 $20$ 的向量的转移可以用矩阵描述。

当一个矩阵 $A$ 的第 $i$ 行第 $j$ 列描述的是走一步 $i$ 转移到 $j$ 的方案数，那么 $(AA)_{i,k}$ 表示的就是走两步 $i$ 转移到 $k$ 的方案数。

直接矩阵快速幂即可，矩阵的系数可以枚举下一步选什么匹配到哪个位置 $O(m)$ 匹配来达到 $O( m^3\Sigma)$，也可以 KMP 来达到 $O( m\Sigma)$。

（矩阵乘的复杂度太高了，以至于求初始矩阵直接暴力都行。）

T7 P4600 [HEOI2012] 旅行问题

ACAM 上 DP 结束力。

下面是喜闻乐见的数据结构环节。

求两个 Trie 节点对应串的最长公共后缀，这个后缀必须是某个串的前缀。

表面上看后一个限制让这个题变难了，实际上没了它还做不了，刚好卡了一下fail树的定义。

就是fail树上的lca。

T8 P2414 [NOI2011] 阿狸的打字机

这个题很妙。

给定一棵 Trie，离线求一个节点在另一个节点中的出现次数。

这个东西很难求。

考虑转化，（$s$ 在 $t$ 中的出现次数）就是（$t$ 的所有前缀的（某个后缀与 $s$ 相等）成立的个数）。

魔法结束。

翻译成人话：所有前缀 -> Trie 上祖先 | 前缀的后缀与 $s$ 相等 -> fail 树上 $s$ 子树中有该前缀 | 成立的个数 -> +1。

所以我们对于询问 $(x,y)$ 要求（Trie 树上 $y$ 及其祖先对应的 fail 树节点）在（fail 树中 $x$ 子树内出现的个数）。

能离线，就比较好做了。

首先（fail 树中 $x$ 子树内出现的个数）用dfn转化成序列问题，用树状数组做。

现在问题就是要遍历 Trie，使得遍历到 $y$ 的时候 $y$ 和其祖先都在树状数组里，这样就可以回答询问了。

用dfs栈即可，进入一个点加入树状数组，离开一个点的时候删掉。

T9 无原题，昨天 F 我的做法

没想到昨天考场上写的巨大难玩意这么快就出了。

多了个在线多组询问，直接把静态树上差分换成树状数组。

（听老哥说好像可以cdq？）

后记

关于 ACAM 的两个问题：

1. 模式串可重叠匹配好做，那对于每一个模式串来说不能重叠能不能快速做呢？

遗憾的是，只有 $O(n\sqrt n\log n)$ 做法。

把每个 ACAM 节点被文本串匹配的位置记录下来（在 fail 树上使用启发式合并）。

然后对于每个 ACAM 节点中模式串的位置贪心在这个集合上面取，每次二分到下一个被匹配的位置，看起来是 $O(n^2\log n)$，但实际上可以均摊证明是 $O(n\sqrt n\log n)$。

因为可以证明一个节点的

2. 难度更上一层楼：如果模式串之间相互影响，所有模式串之间不能重叠，求最多匹配个数/最大匹配长度怎么做呢？

你别说你还真别说。

有简单 $O(n)$ 做法。

首先对于每个文本串节点，求出它能匹配的最短后缀的长度（fail 树上最浅的有意义祖先）。

然后相当于对文本串进行一个序列 DP。