【bzoj1030】[JSOI2007]文本生成器
标签：main can 正整数 大写 zoj 节点 注意 algorithm 并且
JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，
他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文
章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，
那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的
标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6
生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？
Input
输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包
含英文大写字母A..Z
Output
一个整数，表示可能的文章总数。只需要知道结果模10007的值。
题解：
很经典的dp题，我们可以设dp【i】【j】表示处理到文本串的第i位时匹配到AC自动机的j节点的失败方案数，那么初始状态就是匹配到0位，位于初始节点的方案数，显然是1，不然后面都是0了，然后枚举当前每种可能的字母，放到自动机上跑，跑到的节点，显然就多匹配一位，将方案数量移交给他就可以了，不过注意，如果是单词节点或者包含单词点那么显然此时方案数要被清零，用continue实现，末状态就是匹配到最后一个字符，每个节点都有可能，所以求个和。答案就用总方案数减一下就可以了。
代码：
#include
#include
#include
#include
#include
#includeusing namespace std;
const int mod=10007;
int tr[5000][26],f[5000];
char a[500];
bool b[5000];
int n,m,num=0,dp[300][5000],tot=1,ans=0;
void cl(){
memset(b,0,sizeof(b));
memset(tr,0,sizeof(tr));
memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
}
void insert(char x[]){
int now=0,len=strlen(x);
for(int i=0;i){
int to=x[i]-‘A‘;
if(!tr[now][to]) tr[now][to]=++num;
now=tr[now][to];
}
b[now]=1;
}
void bfs(){
queueint> q;
f[0]=0;
q.push(0);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i26;i++){
int numto=tr[now][i],j=f[now];
if(!numto) continue;
while(j&&!tr[j][i]) j=f[j];
if(tr[j][i]!=numto) f[numto]=tr[j][i];
if(b[tr[j][i]]) b[numto]=1;
q.push(numto);
}
}
}
void DP(){
dp[0][0]=1;//
for(int i=1;i){
for(int j=0;j){
if(!dp[i-1][j]||b[j]) continue;
for(int x=0;x25;x++){
int h=j;
while(h&&!tr[h][x]) h=f[h];
h=tr[h][x];
dp[i][h]=(dp[i-1][j]+dp[i][h])%mod;
}
}
}
}
int main(){
cl();
scanf("%d%d",&n,&m);
for(int i=1;i){
scanf("%s",&a);
insert(a);
}
bfs();
DP();
for(int i=1;i26)%mod;
for(int i=0;iif(b[i]==0)ans=(ans+dp[m][i])%mod;
printf("%d",(tot-ans+mod)%mod);
}
【bzoj1030】[JSOI2007]文本生成器
标签：main can 正整数 大写 zoj 节点 注意 algorithm 并且
原文地址：http://www.cnblogs.com/renjianshige/p/7173523.html
评论