首页 > 代码库 > 【bzoj1030】: [JSOI2007]文本生成器 字符串-AC自动机-DP
【bzoj1030】: [JSOI2007]文本生成器 字符串-AC自动机-DP
【bzoj1030】: [JSOI2007]文本生成器
首先把匹配任意一个的个数的问题转化为总个数-没有一个匹配的个数
先构造AC自动机,然后枚举每一位的字母以及在自动机上的位置
f[i][j]为第i位在j的位置且没有匹配过任何一个串的个数
然后26^m-sum(f[m][j])就是答案
还有就是当p->fail一直到root的路径上只要有一个点是一个串的终点那么点f[i][p]就要ban掉 因为这个WA了好多次
1 /* http://www.cnblogs.com/karl07/ */ 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 9 #define P 10007 10 struct trie{ 11 trie *next[26],*fail; 12 int th,w; 13 }t[6005],*root=t,*NEW=t,*q[6005]; 14 15 int n,m,l,r,ans; 16 int f[105][6005]; 17 char s[105]; 18 19 trie *new1(){NEW++; NEW->th=NEW->w=0; return NEW;} 20 21 #define pnf p->next[i]->fail 22 #define pn p->next[i] 23 trie *insert(trie *p,int i,int w){ 24 if (!pn) pn=new1(); 25 pn->w|=w; 26 return pn; 27 } 28 29 void build_fail(){ 30 trie *p=q[0]=root; 31 for (int i=0;i<26;i++) if (pn) pnf=p,q[++r]=pn,pn->th=r; 32 while (l<r){ 33 p=q[++l]; 34 for (int i=0;i<26;i++){ 35 if (pn){ 36 q[++r]=pn,pn->th=r; 37 for (pnf=p->fail ; pnf!=root && !pnf->next[i] ; pnf=pnf->fail); 38 if (pnf->next[i]) pnf=pnf->next[i]; 39 pn->w|=pnf->w; 40 } 41 } 42 } 43 } 44 45 int Q_pow(int x,int y){ 46 int ans=1; 47 for (;y; x=x*x%P , y=y>>1 ) if (y&1) ans=ans*x%P; 48 return ans; 49 } 50 void dp(){ 51 f[0][0]=1; 52 for (int k=0;k<m;k++){ 53 for (int j=0;j<=r;j++) if (f[k][j] && !q[j]->w){ 54 for (int i=0;i<26;i++){ 55 trie *p=q[j]; 56 while (!pn && p!=root) p=p->fail; 57 if (pn) p=pn; 58 f[k+1][p->th]=(f[k+1][p->th]+f[k][j])%P; 59 } 60 } 61 } 62 for (int i=0;i<=r;i++) if (!q[i]->w) ans=(ans+f[m][i])%P; 63 printf("%d\n",(Q_pow(26,m)-ans+P)%P); 64 } 65 #undef pn 66 #undef pnf 67 68 int main(){ 69 scanf("%d%d",&n,&m); 70 for (int i=1;i<=n;i++){ 71 scanf("%s",s); 72 int j=0,l=strlen(s); 73 for (trie *p=root;j<l;j++) p=insert(p,s[j]-‘A‘,j==l-1); 74 } 75 build_fail(); 76 dp(); 77 return 0; 78 }
【bzoj1030】: [JSOI2007]文本生成器 字符串-AC自动机-DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。