AC 自动机上 DP

$\text{Analysis}$

做了几道题后发现挺套路的

涉及统计或构造文本串与众多模式串匹配产生贡献或存在限制时的 $DP$

一般设 $f[i][j]$ 表示考虑到文本串第 $i$ 位，在自动机上的 $j$ 位置

加上 $j$ 这一维，把自动机的弄进 $DP$ 里，方便处理与匹配相关的限制

下面是几道题（按我的做题顺序

$\text{[JSOI2007]}$ 文本生成器

考虑容斥，所有的方案减去一个模式串都不能出现的方案

$DP$ 计算一个模式串都不能出现的方案，即在自动机上不能走到模式串结尾的结点

设 $f[i][j]$ 表示考虑到文本串第 $i$ 位，走到自动机 $j$ 位置时的答案

那么枚举当前位填的字母，考虑能不能填

能不能填的判断方法，就是填了之后的自动机的位置，它以及跳 $fail$ 后遇到的结点均不能是模式串结尾的结点

这个很好理解

然后就没了

$\text{Code}$

#include <cstdio>

#include <cstring>

#define IN inline

using namespace std;

const int P = 10007, N = 6005;

int n, m, size = 1;

int tr[N][26], vis[N], Q[N], fail[N], f[105][N];

char s[105];

IN void insert() {

	int len = strlen(s), u = 1, c;

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

		c = s[i] - 'A';

		if (!tr[u][c]) tr[u][c] = ++size;

		u = tr[u][c];

	}

	vis[u] = 1;

}

IN void build() {

	int h = 0, t = 0;

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

		if (tr[1][i]) fail[Q[++t] = tr[1][i]] = 1; else tr[1][i] = 1;

	while (h < t) {

		int now = Q[++h];

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

			if (tr[now][i]) vis[tr[now][i]] |= vis[fail[tr[now][i]] = tr[fail[now]][i]], Q[++t] = tr[now][i];

			else tr[now][i] = tr[fail[now]][i];

	}

}

IN void Add(int &x, int y) {if ((x += y - P) < 0) x += P;}

IN void Dec(int &x, int y) {if ((x -= y) < 0) x += P;}

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i++) scanf("%s", s), insert();

	build(), f[0][1] = 1;

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

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

			for(int k = 0; k < 26; k++)

			if (!vis[tr[j][k]])

				Add(f[i + 1][tr[j][k]], f[i][j]);

	int ans = 1;

	for(int i = 1; i <= m; i++) ans = 26LL * ans % P;

	for(int i = 1; i <= size; i++) Dec(ans, f[m][i]);

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

}

$\text{[SDOI2014]}$ 数数

尝试数位 $DP$，发现不行

关于不能出现匹配，弄进 $AC$ 自动机里就好了

具体设 $f[i][j][l][k]$ 表示到了第 $i$ 位，自动机 $j$ 的位置上，是否有高位标记，是否有前导零

转移很显然

关于模式串的前导零，在自动机上走时，如果有前导零，那么接下来若填 $0$，则自动机上的状态应还处于根处

因为压根就没开始。

不填 $0$ 的话，应从根出发走到相应的儿子结点

所以我改变了下枚举顺序

不过这题数据挺垃圾的

一些奇妙的甚至错误的处理方式都能 $AC$

$\text{Code}$

#include <cstdio>

#include <cstring>

#define IN inline

using namespace std;

const int N = 1505, P = 1e9 + 7;

int m, size, tr[N][11], fail[N], Q[N], tag[N], f[N][N][2][2], a[N];

char n[N], s[N];

IN void insert() {

	int len = strlen(s), u = 0, c;

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

		c = s[i] - '0';

		if (!tr[u][c]) tr[u][c] = ++size;

		u = tr[u][c];

	}

	tag[u] = 1;

}

IN void build() {

	int h = 0, t = 0, now;

	for(int i = 0; i < 10; i++) if (tr[0][i]) Q[++t] = tr[0][i];

	while (h < t) {

		now = Q[++h];

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

			if (tr[now][i]) tag[tr[now][i]] |= tag[fail[tr[now][i]] = tr[fail[now]][i]], Q[++t] = tr[now][i];

			else tr[now][i] = tr[fail[now]][i];

	}

}

IN void Add(int &x, int y) {if ((x += y - P) < 0) x += P;}

int main() {

	scanf("%s%d", n + 1, &m);

	for(int i = 1; i <= m; i++) scanf("%s", s), insert();

	build(), f[0][0][1][1] = 1;

	int len = strlen(n + 1);

	for(int i = 1; i <= len; i++) a[i] = n[i] - '0';

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

		for(int l = 0; l < 2; l++)

			for(int k = 0; k <= (l ? a[i + 1] : 9); k++) {

				if (!tag[tr[0][k]]) Add(f[i + 1][k ? tr[0][k] : 0][l & (k == a[i + 1])][!k], f[i][0][l][1]);

				for(int j = 0; j <= size; j++)

					if (!tag[tr[j][k]]) Add(f[i + 1][tr[j][k]][l & (k == a[i + 1])][0], f[i][j][l][0]);

			}

	int ans = 0;

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

		for(int j = 0; j < 2; j++)

			for(int k = 0; k < 2; k++) Add(ans, f[len][i][j][k]);

	printf("%d\n", (ans - 1 + P) % P);

}

$\text{[USACO12JAN]Video Game G}$

这个题就一样一样的了

要初始化

$\text{Code}$

#include <cstdio>

#include <iostream>

#include <cstring>

#define IN inline

using namespace std;

const int N = 305, INF = 0x3f3f3f3f;

int n, m, size;

int tag[N], tr[N][3], fail[N], Q[N], f[N << 2][N];

char s[21];

IN void insert() {

	int len = strlen(s), u = 0, c;

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

		c = s[i] - 'A';

		if (!tr[u][c]) tr[u][c] = ++size;

		u = tr[u][c];

	}

	tag[u] = 1;

}

IN void build() {

	int h = 0, t = 0, now;

	for(int i = 0; i < 3; i++) if (tr[0][i]) Q[++t] = tr[0][i];

	while (h < t) {

		now = Q[++h];

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

			if (tr[now][i]) tag[Q[++t] = tr[now][i]] += tag[fail[tr[now][i]] = tr[fail[now]][i]];

			else tr[now][i] = tr[fail[now]][i];

	}

}

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i++) scanf("%s", s), insert();

	memset(f, -INF, sizeof f);

	build(), f[0][0] = 0;

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

		for(int j = 0; j <= size; j++)

			for(int k = 0; k < 3; k++)

				f[i + 1][tr[j][k]] = max(f[i + 1][tr[j][k]], f[i][j] + tag[tr[j][k]]);

	int ans = 0;

	for(int i = 0; i <= size; i++) ans = max(ans, f[m][i]);

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

}

$\text{CF808G Anthem of Berland}$

好久没写 $AC$ 自动机上 $dp$ 了

然而这道题是 $KMP$ 自动机，实际上不过是只有一个串的 $AC$ 自动机

温习了一下写法，注意 $fail$ 初始化！！！

根的儿子结点的 $fail$ 要先初始化为根本身

$\text{Code}$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int tr[N][26], fail[N];

char s1[N], s2[N];

int main() {

    scanf("%s%s", s1 + 1, s2 + 1);

    int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);

    for(int i = 1; i <= len2; i++) tr[i - 1][s2[i] - 'a'] = i;

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

        for(int j = 0; j < 26; j++)

            if (tr[i][j]) fail[tr[i][j]] = tr[fail[i]][j];

            else tr[i][j] = tr[fail[i]][j];

    vector<vector<int>> f(len1 + 1, vector<int>(len2 + 1, -1e9));

    f[0][0] = 0;

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

        for(int j = 0; j <= len2; j++) if (f[i][j] != -1e9) {

            if (s1[i + 1] != '?') {

                int ch = tr[j][s1[i + 1] - 'a'];

                f[i + 1][ch] = max(f[i + 1][ch], f[i][j] + (ch == len2));

                continue;

            }

            for(int k = 0; k < 26; k++)

                f[i + 1][tr[j][k]] = max(f[i + 1][tr[j][k]], f[i][j] + (tr[j][k] == len2));

        }

    }

    int ans = -1e9;

    for(int i = 0; i <= len2; i++) ans = max(ans, f[len1][i]);

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

}

巴特西

AC 自动机上 DP

\(\text{Analysis}\)

\(\text{[JSOI2007]}\) 文本生成器

\(\text{[SDOI2014]}\) 数数

\(\text{[USACO12JAN]Video Game G}\)

\(\text{CF808G Anthem of Berland}\)

最新文章

热门文章