「JSOI2007」文本生成器 - AC自动机 + DP

Link : 1030: [JSOI2007]文本生成器

题面

Description

JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章——

也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6 生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?

Input

输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固定长度M;以下N行,每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A..Z

Output

一个整数,表示可能的文章总数。只需要知道结果模10007的值。

Sample Input

1
2
3
2 2
A
B

Sample Output

1
100

HINT

Source

题解

直接考虑有多少包含匹配串的文本串是很难算的, 所以考虑多少 包含匹配串的文本串, 算出来之后用 26^m 减去就好了

首先建出 AC 自动机

包含匹配串的文本串可以通过在自动机上 DP 来求出, 不包含匹配串的文本串也就是在自动机上跑不到串的结尾, 于是令 \text{dp}[i,j] 表示对于前 i 个字符, 在节点 j , 没有到结尾的方案数, 显然就有对于 非串结尾的 节点 p 以及其父亲 q , 有

\text{dp}[i,p]=\text{dp}[i,p]+\text{dp}[i-1,q]

就做完了

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
#include <bits/stdc++.h>

const int CHAR_SET = 26;
const int MAXN = 100000 + 100;
const int MOD = 10007;
const int LEN = 100 + 10;

struct Node {
int ch[CHAR_SET];
int fail;
int cnt, siz;
int vis;
};

int tot;
Node t[MAXN];

int pow (int base, int p) {
int ret = 1;
while (p) {
if (p & 1) ret = (ret * base) % MOD;
base = (base * base) % MOD; p = p >> 1;
}
return ret;
}

void insert (std::string S) {
int len = S.length(), rt = 0;
for (int i = 0; i < len; i++) {
int c = S[i] - 'A';
if (!t[rt].ch[c]) t[rt].ch[c] = ++tot;
rt = t[rt].ch[c];
t[rt].siz++;
}
t[rt].cnt++;
t[rt].vis |= 1;
}

void bfs () {
std::queue <int> q;
q.push(0);
while (!q.empty()) {
int now = q.front(); q.pop();
int k = t[now].fail;
for (int i = 0; i < CHAR_SET; i++) {
int to = t[now].ch[i];
if (!to) {
t[now].ch[i] = t[k].ch[i];
continue;
}
q.push(to);
t[to].vis |= now ? t[t[k].ch[i]].vis : 0;
t[to].fail = now ? t[k].ch[i] : 0;
}
}
}

int n, m;
std::string str;

int dp[LEN][MAXN];

void solve () {
dp[0][0] = 1;
for (int i = 1; i <= m; i++) // length
for (int j = 0; j <= tot; j++) // AC
for (int c = 0; c < CHAR_SET; c++) { // char
if (t[t[j].ch[c]].vis) continue;
dp[i][t[j].ch[c]] = (dp[i][t[j].ch[c]] + dp[i - 1][j]) % MOD;
}
}

int main () {
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> str;
insert (str);
}
bfs();
solve();

int ans = 0;
for (int i = 0; i <= tot; i++) ans = (ans + dp[m][i]) % MOD;
std::cout << (pow(26, m) - ans + MOD) % MOD;
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!