首页 > 代码库 > bzoj 1030: [JSOI2007]文本生成器 (ac自己主动机上的dp)
bzoj 1030: [JSOI2007]文本生成器 (ac自己主动机上的dp)
1030: [JSOI2007]文本生成器
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2635 Solved: 1090
[Submit][Status][Discuss]
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
2 2
A
B
A
B
Sample Output
100
ac自己主动机上的dp
dp[0][i][j]表示到第i位，以第j个状态结束不符合条件的串的个数
dp[1][i][j]表示到第i位，以第j个状态结束符合条件的串的个数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6005;
const int MOD = 10007;
int que[N], fr, ta;
struct ACM {
int cnt;
int nxt[N][26], sum[N], fail[N];
void init() {
for(int i = 1; i <= cnt; ++i) {
sum[i] = fail[i] = 0;
for(int j = 0; j < 26; ++j)
nxt[i][j] = 0;
}
cnt = 1;
for(int i = 0; i < 26; ++i) nxt[0][i] = 1;
}
void insert(string str) {
int now = 1;
int len = str.length();
for(int i = 0; i < len; ++i) {
if(nxt[now][str[i] - ‘A‘] == 0) nxt[now][str[i] - ‘A‘] = ++cnt;
now = nxt[now][str[i] - ‘A‘];
}
sum[now] = 1;
}
void build_fail() {
fr = ta = 0;
que[ta++] = 1;
fail[1] = 0;
while(fr != ta) {
int now = que[fr++];
for(int i = 0; i < 26; ++i) {
int x = nxt[now][i];
if(x == 0) continue;
int tmp = fail[now];
while(nxt[tmp][i] == 0) tmp = fail[tmp];
fail[x] = nxt[tmp][i];
que[ta++] = x;
}
}
}
void debug() {
for(int i = 1; i <= cnt; ++i) {
cout<<i<<": "<<"fail = "<<fail[i]<<" [ ";
for(int j = 0; j < 26; ++j) {
if(nxt[i][j]) cout<<char(j + ‘A‘)<<‘,‘<<nxt[i][j]<<‘ ‘;
}
puts("]");
}
}
void gao(int, int);
} acm;
int dp[2][105][N];
void ACM::gao(int n, int m) {
build_fail();
//debug();
memset(dp, 0, sizeof(dp));
dp[0][0][1] = 1;
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= cnt; ++j) {
int u = j;
for(int k = 0; k < 26; ++k) {
int v = u;
while(nxt[v][k] == 0) v = fail[v];
v = nxt[v][k];
if(sum[v]) {
dp[1][i][v] = (dp[1][i][v] + dp[1][i - 1][u] + dp[0][i - 1][u]) % MOD;
dp[0][i][v] += 0;
} else {
dp[1][i][v] = (dp[1][i][v] + dp[1][i - 1][u]) % MOD;
dp[0][i][v] = (dp[0][i][v] + dp[0][i - 1][u]) % MOD;
}
}
}
}
int ans = 0;
for(int i = 1; i <= cnt; ++i)
ans = (ans + dp[1][m][i]) % MOD;
cout<<ans<<endl;
}
string str[65];
bool ok(int x, int n) {
int len = str[x].length();
for(int i = 0; i < n; ++i) {
if(i == x) continue;
int pos = str[x].find(str[i]);
if(pos >= 0 && pos < len) return false;
}
return true;
}
int main() {
int n, m;
cin>>n>>m;
acm.init();
for(int i = 0; i < n; ++i) {
cin>>str[i];
}
sort(str, str + n);
n = unique(str, str + n) - str;
for(int i = 0; i < n; ++i) {
if(ok(i, n)) acm.insert(str[i]);
}
acm.gao(n, m);
return 0;
}
bzoj 1030: [JSOI2007]文本生成器 (ac自己主动机上的dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。