重习 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)getsdelta(fail(x), c))。从而一些查询 & 构建 的时候就根本不用直接跳 (fail) 应付失配，优化了效率和代码难度。

  • 构建 AC 自动机的代码非常简洁（复杂度 (O(n imes |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 imes 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) e ext{null}: f(i,j) o 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 o 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 imes sum_i|s_i|))。

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

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

  • 现在 (m) 的规模边的很大，怎么办？我们先把问题做一步转化：从根状态结点走 (m) 步到任意 非禁止状态 的方案数。那么我们将建出的 Trie 图看做一个 有向图。然后就是经典的“从 (s) 走 (m) 条边到 (t) 的走法数”问题。

  • 很显然地考虑 邻接矩阵（(g)） 表示这个图，然后对其做 (m) 次幂。那么 (g_{i,j}) 就是 (i) 走 (m) 步到达 (j) 的方案数。

  • 那么答案即为 (sum_{xin{ ext{ACAM}}}g_{Q,x})，其中 (Q) 为根状态。

  • 再用 矩阵快速幂 优化幂运算，复杂度为 (O((sum_i|s_i|)^3log 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
", 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(nlog n)/O(nlog^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) 的前缀 (1sim x) 中有几个模式串可以作为其后缀，同理对后缀 (xsim |t|) 定义 (g) 表示几个可以作为前缀。答案可以表示为 (sum_{iin[1, n)} f(i) imes g(i+1))。
  • 由于 (f) 将字符串翻转就是 (g)，这里只提一下 (f) 的求法。首先对 (s_1,s_2, cdots,s_n) 建 AC 自动机，然后 (t) 在上面跑转移。走到一个位置，当前 (f) 的值就是 (fail) 树上的子树和。(g) 的话就把所有串翻转再跑一遍。
  • 复杂度 (O(sum_i|s_i|+|t|))

后记

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/-Wallace-/p/acam.html