首页 > 代码库 > BZOJ1030: [JSOI2007]文本生成器
BZOJ1030: [JSOI2007]文本生成器
1030: [JSOI2007]文本生成器
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 1902 Solved: 776
[Submit][Status]
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
题解：
复（xue）习一下AC自动机。
一些注释写在代码里
代码：
View Code
复（xue）习一下AC自动机。
一些注释写在代码里
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1000000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 10007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int t[6010][26],f[110][6010][2],v[6010],go[6010]; 61 char s[110]; 62 queue<int> q; 63 int n,m,tot; 64 inline void insert() 65 { 66 scanf("%s",s+1);int len=strlen(s+1),now=1; 67 for1(i,len) 68 { 69 int x=s[i]-‘A‘; 70 if(!t[now][x])t[now][x]=++tot; 71 now=t[now][x]; 72 } 73 v[now]=1;//标记该节点为危险节点 74 } 75 void bfs()//按bfs序来递推每节点的fail，此处用go数组表示 76 { 77 q.push(1); 78 while(!q.empty()) 79 { 80 int x=q.front(),y,j;q.pop(); 81 for0(i,25) 82 { 83 j=go[x]; 84 while(j&&!t[j][i])j=go[j]; 85 if(t[x][i]) 86 { 87 go[y=t[x][i]]=j?t[j][i]:1;//该节点存在则设置它的fail 88 v[y]=v[y]|v[go[y]];//它的危险符号 89 q.push(y);//更新它的子树的fail 90 }else t[x][i]=j?t[j][i]:1;//没有出边直接补齐 91 } 92 } 93 } 94 void dp() 95 { 96 f[0][1][0]=1; 97 for0(i,m) 98 for1(j,tot) 99 for0(k,25)100 for0(l,1)//l表示匹配还是未匹配101 if(v[t[j][k]])(f[i+1][t[j][k]][1]+=f[i][j][l])%=mod;102 else (f[i+1][t[j][k]][l]+=f[i][j][l])%=mod;103 }104 105 int main()106 107 {108 109 freopen("input.txt","r",stdin);110 111 freopen("output.txt","w",stdout);112 113 n=read();m=read();tot=1;114 for1(i,n)insert();115 bfs();116 dp();117 int ans=0;118 for1(i,tot)(ans+=f[m][i][1])%=mod;119 printf("%d\n",ans);120 121 return 0;122 123 }
BZOJ1030: [JSOI2007]文本生成器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。