「BZOJ1030」[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
2 2
A
B
A
B
Sample Output
100
题解
f[i][j]表示到第i个位置匹配自动机上第j个结点的方案数
意会一下
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #define mod 10007 using namespace std; int n,m,sz=1,ans1,ans2=1; int a[6001][27],point[6001],q[6001],f[101][6001]; char s[101]; bool danger[6001]; void ins() { int now=1,c; for(int i=0;i<strlen(s);i++) { c=s[i]-'A'+1; if(a[now][c])now=a[now][c]; else now=a[now][c]=++sz; } danger[now]=1; } void acmach() { int t=0,w=1,now; q[0]=1;point[1]=0; while(t<w) { now=q[t++]; for(int i=1;i<=26;i++) { if(!a[now][i])continue; int k=point[now]; while(!a[k][i])k=point[k]; point[a[now][i]]=a[k][i]; if(danger[a[k][i]]) danger[a[now][i]]=1; q[w++]=a[now][i]; } } } void dp(int x) { for(int i=1;i<=sz;i++) { if(danger[i]||!f[x-1][i])continue; for(int j=1;j<=26;j++) { int k=i; while(!a[k][j])k=point[k]; f[x][a[k][j]]=(f[x][a[k][j]]+f[x-1][i])%mod; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=26;i++)a[0][i]=1; for(int i=1;i<=n;i++) { scanf("%s",s); ins(); } acmach(); f[0][1]=1; for(int i=1;i<=m;i++)dp(i); for(int i=1;i<=m;i++) ans2=(ans2*26)%mod; for(int i=1;i<=sz;i++) if(!danger[i])ans1=(ans1+f[m][i])%mod; printf("%d",(ans2-ans1+mod)%mod); return 0; } |
计数器 9720327
OI 课件=>
OI 课件=>
学长，用 for(int i=0;i<strlen(s);i++) 不太好吧qwq
毕竟strlen(s) 是O(n) 的qwq
你说的对，但 s 只有 100
学长，请问如果文章里存在模式串里没有的字母怎么办？统计的时候会不会统计不上啊
没有关系的吧，会一直跳到根？
学长，请问您34行和35行的比一般AC自动机多出来的那个是什么意思呢？不太明白
啊，明白了，不麻烦您了，谢谢。