0%

[JSOI2007] 文本生成器

题目

题目链接

题目大意: 给出 $n$ 个模式串和 $m$, 找出有多少长度为 $m$ 的文本串中包含至少一个模式串. 答案对 $10^4 + 7$ 取模. $1 \le n \le 60, 1 \le m \le 100, 1 \le |S| \le 100$.

思路

将问题转换为求有多少文本串不包含任何一个模式串.

首先建出模式串的 AC 自动机.

考虑在自动机上 DP. 对于自动机上的任何一个叶子节点, 我们发现它一定合法.

如果一个节点在若干次失配以后能到达叶子节点, 也一定合法.

设 $f(i, j)$ 为长度为 $i$, 当前节点为 $j$ 时不合法的方案数. 如果 $j$ 的某一个儿子不合法就可以进行转移, f[i + 1][tr[j][k]] += f[i][j].

最后答案即为 $26 ^ m - \sum f(m, i)$.

代码

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
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;
typedef unsigned long long uLL;

const int mod = 1e4 + 7;

int tr[6010][26], f[110][6010];
int fail[6010];
int n, m, tot, ans;
bool b[6010];

int qPow(int x, int b) {
int s = 1;
while (b) {
if (b & 1) {
s *= x;
s %= mod;
}
x *= x;
x %= mod;
b >>= 1;
}
return s;
}

void insert(char *s) {
int u = 0;
for (int i = 1; s[i]; ++i) {
if (!tr[u][s[i] - 'A']) tr[u][s[i] - 'A'] = ++tot;
u = tr[u][s[i] - 'A'];
}
b[u] = true;
}

void build() {
std::queue<int> q;
for (int i = 0; i < 26; ++i) {
if (tr[0][i]) {
q.push(tr[0][i]);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (tr[u][i]) {
fail[tr[u][i]] = tr[fail[u]][i];
b[tr[u][i]] |= b[fail[tr[u][i]]];
q.push(tr[u][i]);
} else {
tr[u][i] = tr[fail[u]][i];
}
}
}
}

int main() {
read(n), read(m);
char s[110];
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
insert(s);
}
build();
f[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j <= tot; ++j) {
for (int k = 0; k < 26; ++k) {
if (!b[tr[j][k]]) f[i + 1][tr[j][k]] = (f[i + 1][tr[j][k]] + f[i][j]) % mod;
}
}
}
ans = qPow(26, m);
for (int i = 0; i <= tot; ++i) ans = (ans % mod - f[m][i] % mod + mod) % mod;
printf("%d\n", (ans % mod + mod) % mod);
return 0;
}