【复习笔记】重习 AC 自动机

发现已经忘了许多。。。。于是复习一下

基础要点概况

AC 自动机基于 Trie 树 的结构，即构建 AC 自动机前需要先建 Trie。
一个状态中除了转移 \(\delta\) 之外还有失配指针 \(fail\)。\(fail(x)\) 对于的字符串是 \(x\) 对应字符串的 最长真后缀。
要求出 \(fail\) 我们可以 bfs 实现。对于当前状态 \(x\)，设其父亲 \(f\) 通过一个 \(c\) 转移连向 \(x\)，那么我们先看看 \(fail(f)\) 是否存在 \(c\) 转移，如果有那么 \(fail(x)\gets \delta(fail(f),c)\)，否则就看 \(fail(fail(f))\)，再不行继续递归下去。要真没有就直接指向根状态。
但实际上我们都会直接写成 Trie 图，如果一个转移 \(\delta(x, c)\) 不存在，那么就 \(\delta(x, c)\gets\delta(fail(x), c)\)。从而一些查询 & 构建的时候就根本不用直接跳 \(fail\) 应付失配，优化了效率和代码难度。

构建 AC 自动机的代码非常简洁（复杂度 \(O(n\times |\Sigma|)\)，\(n\) 为状态个数，下同）：

void init_fail() {

	for (int i = 0; i < S; i++) ch[0][i] = 1;

	for (Q.push(1); !Q.empty(); ) {

		int x = Q.front(); Q.pop();

		for (int i = 0; i < S; i++)

			if (!ch[x][i]) ch[x][i] = ch[fail[x]][i];

			else Q.push(ch[x][i]), fail[ch[x][i]] = ch[fail[x]][i];

	}

}

AC 自动机最经典的应用就是 多模式串匹配 了：Luogu P3808 【模板】AC自动机（简单版）。先对所有模式串建 AC 自动机，然后从根开始跑文本串：每到达一个点，沿着自己的 \(fail\) 向上跳一遍，答案加上沿途遇到的终止状态的个数。当然，为避免重复统计，可以给走过的位置打一个标记。

询问的参考代码（复杂度 \(O(n)\)）：

int query(char* s) {

	int ans = 0;

	for (int x = 1, i = 0; s[i]; i++) {

		x = ch[x][s[i] - 'a'];

		for (int y = x; y && ~cnt[y]; y = fail[y])

			ans += cnt[y], cnt[y] = -1;

	}

	return ans;

}

然而这样做一些多次询问的题会被卡爆成 \(O(n\times Q)\)，比如要求所有串分别出现的次数时，遇到 aaaaaa...aa 这种，一次转移就要跳 \(O(n)\) 次失配指针。于是引入 \(fail\) 树：对于每个非根状态 \(x\)，都从 \(fail(x)\) 连过来一条边，最终形成 \(fail\) 树。
\(fail\) 树将我跳失配指针的过程实体化了，那么一个状态能更新到 \(x\)，那么说明这个状态在 \(x\) 的 \(fail\) 树上的子树内。这就好办了，我们先将文本串在 AC 自动机上跑一边，沿途更新计数器，然后一个状态对应的 \(fail\) 树 子树和 即为出现次数。

于是这样就是真的线性了，Luogu P5357 【模板】AC自动机（二次加强版）代码：

std::vector<int> adj[N];

int dfs(int x) {

	for (int i = 0; i < (int)adj[x].size(); i++)

		cnt[x] += dfs(adj[x][i]);

	return cnt[x];

}

void query(char* s) {

	for (int x = 1, i = 0; s[i]; i++)

		++cnt[x = ch[x][s[i] - 'a']];

	dfs(1);

}

进阶应用（套路）

套路 1：AC 自动机相关 dp

【JSOI2007】文本生成器：给你若干个模式串，求至少包含一个模式串的长度为 \(m\) 的文本串个数。

首先一个简单的容斥，答案为 \(m^{|\Sigma|}\) 减去不包含任何一个模式串的个数。
然后令 \(f(i,j)\) 为当前长度为 \(i\) 且走到状态 \(j\) 的方案数。那么转移显然是 \(\forall \delta(j,c)\ne \text{null}: f(i,j) \to f(i+1,\delta(j,c))\)，并且 不能转移到有结束标记 的状态。

但这样还不行，要得到一个字符串，我们不只有这一个状态可以作为终点。如果当前代表的字符串的最长真后缀 \(fail(x)\) 不能走，那么当前状态 \(x\) 也不能走，因为 前者必然被后者所包含。那么考虑稍微更改一下构建的实现：

void build() {

	std::queue<int> Q;

	for (int i = 0; i < S; i++) ch[0][i] = 1;

	for (Q.push(1); !Q.empty(); ) {

		int x = Q.front(); Q.pop();

		for (int i = 0; i < S; i++) {

			if (!ch[x][i]) { ch[x][i] = ch[fail[x]][i]; continue; }

			Q.push(ch[x][i]);

			fail[ch[x][i]] = ch[fail[x]][i];

			end[ch[x][i]] |= end[fail[ch[x][i]]]; // <-

		}

	}

}

那么 dp 的过程就比较显然了：先 \(1\to m\) 枚举长度，再考虑所有的状态，对于每个状态枚举所有可行转移。

f[0][1] = 1;

for (int i = 1; i <= m; i++)

	for (int j = 1; j <= total; j++)

		for (int c = 0; c < S; c++) if (!end[ch[j][c]])

			(f[i][ch[j][c]] += f[i - 1][j]) %= mod;

时间复杂度 \(O(m\times \sum_i|s_i|)\)。

套路 2：套路 1 的矩阵优化

【POJ 2778】DNA Sequence：给定 \(n\) 个禁止串，求长度为 \(m\) 且不含任何一个禁止串的字符串个数。\(1\le m\le 2\times 10^9\)

现在 \(m\) 的规模边的很大，怎么办？我们先把问题做一步转化：从根状态结点走 \(m\) 步到任意 非禁止状态 的方案数。那么我们将建出的 Trie 图看做一个 有向图。然后就是经典的“从 \(s\) 走 \(m\) 条边到 \(t\) 的走法数”问题。
很显然地考虑 邻接矩阵（\(g\)）表示这个图，然后对其做 \(m\) 次幂。那么 \(g_{i,j}\) 就是 \(i\) 走 \(m\) 步到达 \(j\) 的方案数。
那么答案即为 \(\sum_{x\in{\text{ACAM}}}g_{Q,x}\)，其中 \(Q\) 为根状态。

再用 矩阵快速幂 优化幂运算，复杂度为 \(O((\sum_i|s_i|)^3\log m)\)：

Matrix f, g;

for (int i = 1; i <= total; i++) if (!end[i])

    for (int j = 0; j < S; j++) if (!end[ch[i][j]])

        ++f.e[i][ch[i][j]];

for (int i = 1; i <= total; i++)

    g.e[i][i] = 1;

for (; m; m >>= 1, f = f * f)

    if (m & 1) g = g * f;

int ans = 0;

for (int i = 1; i <= total; i++)

    (ans += g.e[1][i]) %= mod;

printf("%d\n", ans);

套路 3：转化为树上统计问题

【Codeforces 163E】e-Government：给定 \(k\) 个字符串 \(s_1, s_2, \cdots, s_k\)，要求维护一个字符串集 \(S\)，一开始 \(k\) 个字符串都在 \(S\) 中，现有 \(n\) 次操作，每次会加入或移除 \(k\) 个字符串中的一个，或者询问一个文本串求出 \(S\) 中每个串匹配次数之和。

首先 AC 自动机并不能很方便地支持动态加，更何况删除，显然是一开始就要建好 AC 自动机。
然后不能想到修改时直接在对应位置的计数器 \(\pm 1\)，然后统计贡献直接暴跳 \(fail\)。然而这个 Naive 的想法早就被卡了。
于是想二次加强版一样考虑建出 \(fail\) 树，然后就是跳祖先累加贡献，也就是 链上求和。
所以说现在要维护一颗树，支持链求和 & 单点修改。树剖或括号序加树状数组都可，复杂度 \(O(n\log n)/O(n\log^2 n)\)。
以及【NOI2011】阿狸的打字机也用了类似的思想，推荐写一下。

杂题选做

【POI2000】病毒

给定 \(n\) 个禁止串，求是否存在无限长的串，不包含任意一个禁止串。

这个题非常神奇，它要求尽量不匹配。
于是我们将计就计，在 AC 自动机上跑的时候，尽量避开禁止状态。注意，这里“禁止”的处理也需要想“文本生成器”那样修改构建函数。
然而“尽量避开”是个很模糊的概念，不过在这里显然是指可以在 AC 自动机下无限地走下去。
那么，其实只要找到一个 经过根状态的环即可。一次 Dfs 搞定。

【Codeforces 1202E】You Are Given Some Strings...

给定一个字符串 \(t\) 以及 \(n\) 个模式串 \(s_1, s_2, \cdots, s_n\)。设 \(f(s, t)\) 为字符串 \(t\) 在 \(s\) 中的出现次数，\(s_i+s_j\) 表示 \(s_i\) 在后面追加 \(s_j\) 所得到的字符串。求 \(\sum_{i,j}f(t, s_i+s_j)\)。

首先，如果其中一个 \(s_i+s_j\) 匹配上了，那么必然在 \(t\) 中存在一个断点，使得前半部分的一个后缀为 \(s_i\)，后半部分的一个前缀为 \(s_j\)。
那么考虑枚举这个断点 \(x\)，记 \(f(x)\) 为 \(t\) 的前缀 \(1\sim x\) 中有几个模式串可以作为其后缀，同理对后缀 \(x\sim |t|\) 定义 \(g\) 表示几个可以作为前缀。答案可以表示为 \(\sum_{i\in[1, n)} f(i)\times g(i+1)\)。
由于 \(f\) 将字符串翻转就是 \(g\)，这里只提一下 \(f\) 的求法。首先对 \(s_1,s_2, \cdots,s_n\) 建 AC 自动机，然后 \(t\) 在上面跑转移。走到一个位置，当前 \(f\) 的值就是 \(fail\) 树上的子树和。\(g\) 的话就把所有串翻转再跑一遍。
复杂度 \(O(\sum_i|s_i|+|t|)\)

巴特西