标签：AC int 笔记提交 fail 自动机 dp

1.KMP 自动机

1.1 内容

KMP 自动机本质上就是单串的 AC 自动机。

我们定义转移函数为：

\[\delta(i, c) = \begin{cases} \delta(\pi_i, c)&s_{i+1} \not= c\\ i + 1&s_{i+1} = c \end{cases} \]

其实也就是模拟了 KMP 的整个过程。

1.2 应用

自动机上跑 dp 是最常见的应用，一般会有一维是自动机的状态。

对于一些问题还可以用矩阵优化。

CF808G Anthem of Berland

设 \(dp(i,j)\) 表示确定了前 \(i\) 个字符，当前在 \(j\) 状态，最多匹配了几次。转移就是简单的线性 dp。

提交记录

P3193 [HNOI2008] GT考试

设 \(dp(i,j)\) 表示确定了前 \(i\) 个字符，当前在 \(j\) 状态的方案数。转移用矩阵快速幂优化。

提交记录

P3082 [USACO13MAR] Necklace G

设 \(dp(i,j)\) 表示前 \(i\) 个确定，在 \(j\) 状态，最多保留几个。

提交记录

2. AC 自动机

2.1 内容

假设现在我们是一个多串匹配的问题，我们该如何建立自动机。

首先，我们需要将所有串建成一颗 Trie，然后我们定义转移函数：

\[\delta(i, c) = \begin{cases} child[i][c]&child[i][c] \text{ exist}\\ \delta(fail_i, c)&\text{Otherwise.} \end{cases} \]

其中的 fail 称作失陪指针，和单串中的 \(\pi\) 是类似的，指向最长的真后缀。

但是 AC 自动机其实有两个和重要的东西：转移表和 fail 树，转移表就是上面的东西，而 fail 树指的是每个点向 fail 连边形成的树。这个在解决问题时帮助很大。

我们考虑 5357 【模板】AC 自动机的问题：

给定 \(S\) 和 \(t_1 \sim t_n\)，求每个 \(t_i\) 在 \(S\) 中出现次数。

我们对 \(t\) 建出 AC 自动机，然后我们跑一边 \(S\)，将其经过的所有点都打上标记。

我们观察 fail 树会发现每个串出现当且仅当经过的是子树内的点。于是我们求子树和就能得出问题的答案。

建立 AC 自动机的过程可以用 bfs 来建，同时由于我们遍历的顺序是字典序，所以我们可以把队列保留下来，求子树和时倒序求即可。

给出代码：

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int S = 26;
const int M = 2e6 + 5;

int n;
int ch[N][S] = {{0}}, fail[N] = {0}, cnt;
int ed[N] = {0}; // ed[i]: 第 i 个模式串的节点
int f[N] = {0}; // f[i]: 节点 i 的经过次数 ==> 子树 i 的经过次数
int q[N] = {0}, fr, ba;
char s[M];

void insert(int x) {//第 x 个模式串
	int now = 0;
	for (int i = 0; s[i]; i++) {
		if (!ch[now][s[i] - 'a'])
			ch[now][s[i] - 'a'] = ++cnt;
		now = ch[now][s[i] - 'a'];
	}
	ed[x] = now;
}


void getfail() {
	fr = 1, ba = 0;
	for (int i = 0; i < S; i++)
		if (ch[0][i])
			q[++ba] = ch[0][i];
	while (fr <= ba) {
		int x = q[fr++];
		for (int i = 0; i < S; i++)
			if (!ch[x][i])
				ch[x][i] = ch[fail[x]][i];
			else {
				fail[ch[x][i]] = ch[fail[x]][i];
				q[++ba] = ch[x][i];
			}
	}
}

void run() {
	int now = 0;
	for (int i = 0; s[i]; i++) {
		now = ch[now][s[i] - 'a'];
		++f[now];
	}
}


int main() {
	cnt = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		insert(i);
	}
	getfail();
	scanf("%s", s);
	run();
	for (int i = cnt; i >= 1; i--)
		f[fail[q[i]]] += f[q[i]];
	for (int i = 1; i <= n; i++)
		printf("%d\n", f[ed[i]]);
	return 0;
}