Fork me on GitHub

Bzoj 1030(AC自动机+区间DP)

bzoj 1030
题意:构造主串长为$m$,使得主串包含所有的$n$个模式串,求主串有多少种可能性。

首先可以转化问题,主串的所有可能性个数$26^m$,所有求出不包含所有的$n$个模式串的主串可能个数,补集转化即可($26^m-$不包含个数)。
然后多模式串想到AC自动机,方案数想到DP。
先把模式串建一个AC自动机,然后每个点如果是串的末尾,则该点标为危险点(即说明根到这个点路径非法,危险点不转移),注意如果失配边指着危险点,那这个点也是危险的。
然后设$dp(i,j)$为考虑了$i$个字符,现在在AC自动机$j$点上的方案数。
$$dp(i,v) = (dp(i,v) + dp(i-1,j))$$
其中$v$点是$ch(j, c)$(不存在则走失配边,直到有为止),即从$j$点转移到$v$点
注意$dp(i, x)$中每个$x$互不影响,即没有先后关系,所有$dp(i)$都是从$dp(i - 1)$转移而来的,AC自动机上的点只是作为一个方向指引
如果主串字母出现不在AC自动机上的字母,那么v是会到根节点(0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MO = 10007, MAXN = 60 * 100 + 10;
int n, m, sz = 60 * 100 + 2;
int f[MAXN], ch[MAXN][30], danger[MAXN], dp[105][MAXN];
char s[105];
void insert(char *s) {
int now = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
int c = s[i] - 'A';
if (!ch[now][c]) ch[now][c] = ++sz;
now = ch[now][c];
if (i == len - 1) danger[now] = true;
//这个点是危险的
}
}
void getFail() {
queue<int> q;
f[0] = 0;
for (int c = 0; c < 26; c++) {
int v = ch[0][c];
if (v) q.push(v), f[v] = 0;
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int c = 0; c < 26; c++) {
int v = ch[u][c];
if (!v) {ch[u][c] = ch[f[u]][c]; continue;}
q.push(v);
int j = f[u]; while (j && !ch[j][c]) j = f[j];
f[v] = ch[j][c];
if (danger[ch[j][c]]) danger[v] = true;//Mistake: danger[v] 而不是 danger[f[v]]
//如果失配边指着危险点,那这个点也是危险的
}
}
}
void cal() {
dp[0][0] = 1;//初始化,主文本第0个字符在0号点上有一个方案
for (int i = 1; i <= m; i++) {//枚举主文本
for (int j = 0; j <= sz; j++) {//枚举每个点
if (danger[j] || !dp[i - 1][j]) continue;
//是危险点,这个节点没有方案就不转移
for (int c = 0; c < 26; c++) {//枚举每条边转移
int v = ch[j][c];
dp[i][v] = (dp[i][v] + dp[i - 1][j]) % MO;
//dp[i - 1][j] 转移到 dp[i][v]
//注意dp[i][x]中每个x互不影响,即没有先后关系,所有dp[i]都是从dp[i - 1]转移而来的,AC自动机上的点只是作为一个方向指引
//如果主串字母出现不在AC自动机上的字母,那么v是会到根节点(0)
}
}
}
}
void clean() {
for (int i = 0; i <= sz; i++) {
for (int j = 0; j < 26; j++) ch[i][j] = 0;
for (int j = 0; j <= m; j++) dp[j][i] = 0;
f[i] = danger[i] = 0;
}
sz = 0;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%s", s);
insert(s);
}
getFail(), cal();
int taki = 1, whw = 0;
for (int i = 1; i <= m; i++) taki = (taki * 26) % MO;
for (int i = 0; i <= sz; i++) if (!danger[i]) whw = (whw + dp[m][i]) % MO;//Mistake: 不是危险的状态才累加
printf("%d\n", (taki - whw + MO) % MO);//补集转化
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
------ 本文结束 ------