NFLS-S20230802 AC 自动机

[toc]

一、AC 自动机和模板

略

Luogu P3808

Luogu P3796

二、AC 自动机和 DP

B.文本生成器

Description

Luogu P4052

Solution

题目要求出至少包含一个模式串的文本串的个数，发现这个玩意很难直接算，从反面考虑，我们计算出不包含任何模式串的文本串个数。

我们先把所有模式串扔到 AC 自动机中，把所有是某个模式串结尾的节点都打上标记，很显然，如果一个节点 $u$ 的 fail 指针所指向的节点 $fail[u]$ 上有标记，那么 $u$ 上面也应该打上标记，这一步可以在构建 AC 自动机的时候完成。

接着我们考虑 DP

$dp[i][cur]$ 表示我们构造到了文本串的第 i 位，并且在自动机上面走到了 cur 号节点且不经过任何被标记的节点的路径数

如果 $ch[cur][k]$ 这个节点没有被标记，那么就可以从 $(i,cur)$ 转移到 $(i+1,ch[cur][k])$

即：$dp[i+1][ch[cur][k]]+=dp[i][cur] (0\le k < 26)$

最后原问题的答案就是 $26^m-\sum dp[m][u]$

C.Video Game

Description

Luogu P3041

Solution

这题看起来和上一题很像！我们考虑改一改 AC 自动机节点里面存的东西，来计算本题的答案。

我们在每个节点上面放一个计数器，表示在 trie 树上这个节点到根的链所组成的字符串包含多少个模式串

还是一样，我们先把所有的模式串都塞到 AC 自动机中，如果一个节点是某个模式串的结尾，那么我们给这个节点上的计数器+1s

在构建 fail 边的时候，把 $u$ 号节点的 fail 指针所指向的节点 $fail[u]$ 的计数器累加到 $u$ 号节点的计数器中。

接着我们考虑 DP ：

$dp[i][cur]$ 表示当前在 AC 自动机的 cur 号节点，文本串的长度为 i ，最多包含了多少个模式串(同一个串可重复贡献)

$(i,cur)$ 可以转移到 $(i+1,ch[cur][k])$ ，所以 $dp[i+1][ch[cur][k]]+=dp[i][cur] (0 \le k <3)$

最后，问题的答案为 $\max_{cur} dp[m][cur]$

D. 最短母串

Description

Luogu P2322

Solution

发现模式串的个数很小 $(n\le 12)$ ，考虑一下状压。

我们先构建出 AC 自动机，对于每一个节点放一个变量用来存这个节点是哪些模式串的结尾。

然后我们用 bfs 的方式去打印方案，每次转移到下一个状态的时候，暴力的去跳 fail 指针，统计这个状态所对应的文本串已经包含了哪些模式串，当全部包含的时候打印方案。

由于是通过 bfs 的方式去找答案，这就保证了输出的答案是字典序最小的。

E.密码

Description

Luogu P4045

Solution

先考虑一个问题：为什么是在满足条件的字符串的总数小于等于 42 时才打印方案呢？

哦！因为 42 是生命、宇宙和万物的答案！

很显然不是上面那个原因，首先，如果我们需要打印方案，但是可能存在某些方案中的文本串里面有自由的位置(即不会受到模式串限制的位置)，那么这可能做起来会很麻烦。但是如果题目限制了在总方案数小于等于 42 时才打印方案，我们就不需要担心这个了，因为如果文本串里面存在自由的位置，那么这个位置会对方案数产生 $*26$ 的贡献，而子串之间可以交换位置，那么总方案数就至少为 $2*26=52>42$ ，因此有自由位置时，我们就不用打印方案了。

然后就是很好想的 DP 了。

F. GT考试

Description

Luogu P3193

Solution

抛开字符集的差别，这题和 B 题几乎是一样的，除了…… $N \le 10^9$

所以普通的 DP 不仅会爆掉空间，还会超时，但是我们发现对于这个转移方程，同一行的格子之间不会互相依赖，那么我们就可以用矩阵快速幂去优化这个 DP 转移。