首页 > 代码库 > 【bzoj1030】[JSOI2007]文本生成器
【bzoj1030】[JSOI2007]文本生成器
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的值。
题解:
很经典的dp题,我们可以设dp【i】【j】表示处理到文本串的第i位时匹配到AC自动机的j节点的失败方案数,那么初始状态就是匹配到0位,位于初始节点的方案数,显然是1,不然后面都是0了,然后枚举当前每种可能的字母,放到自动机上跑,跑到的节点,显然就多匹配一位,将方案数量移交给他就可以了,不过注意,如果是单词节点或者包含单词点那么显然此时方案数要被清零,用continue实现,末状态就是匹配到最后一个字符,每个节点都有可能,所以求个和。答案就用总方案数减一下就可以了。
代码:
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> #include<queue> using 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<len;i++){ int to=x[i]-‘A‘; if(!tr[now][to]) tr[now][to]=++num; now=tr[now][to]; } b[now]=1; } void bfs(){ queue<int> q; f[0]=0; q.push(0); while(!q.empty()){ int now=q.front(); q.pop(); for(int i=0;i<26;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<=m;i++){ for(int j=0;j<=num;j++){ if(!dp[i-1][j]||b[j]) continue; for(int x=0;x<=25;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<=n;i++){ scanf("%s",&a); insert(a); } bfs(); DP(); for(int i=1;i<=m;i++) tot=(tot*26)%mod; for(int i=0;i<=num;i++) if(b[i]==0)ans=(ans+dp[m][i])%mod; printf("%d",(tot-ans+mod)%mod); }
【bzoj1030】[JSOI2007]文本生成器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。