BZOJ1030 JSOI2007文本生成器

 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=6005,mod=10007; 5 ll ans1,ans2,f[105][N]; 6 char s[105];int cnt,n,m; 7 queue<int>q; 8 struct node 9 {10 ????int s,v[26],f;11 }t[N];12 void build()13 {14 ????int n=strlen(s);int now=0;15 ????for(int i=0;i<n;++i)16 ????{17 ????????if(t[now].v[s[i]-‘A‘])now=t[now].v[s[i]-‘A‘];18 ????????else{19 ????????????t[now].v[s[i]-‘A‘]=++cnt;now=cnt;20 ????????}21 ????}22 ????t[now].s=1;23 }24 void getfail()25 {26 ????for(int i=0;i<26;++i)27 ????{28 ????????if(t[0].v[i])29 ????????{30 ????????????t[t[0].v[i]].f=0;q.push(t[0].v[i]);31 ????????}32 ????}33 ????while(!q.empty())34 ????{35 ????????int x=q.front();q.pop();36 ????????for(int i=0;i<26;++i)37 ????????{38 ????????????if(t[x].v[i])39 ????????????{40 ????????????????t[t[x].v[i]].f=t[t[x].f].v[i];q.push(t[x].v[i]);41 ????????????}42 ????????????else t[x].v[i]=t[t[x].f].v[i];43 ????????????t[t[x].v[i]].s|=t[t[t[x].v[i]].f].s;44 ????????}45 ????}46 }47 void work()48 {49 ????f[0][0]=1;50 ????for(int i=1;i<=m;++i)51 ????????for(int j=0;j<=cnt;++j){52 ????????????if(t[j].s)continue;53 ????????????for(int k=0;k<26;++k)54 ????????????f[i][t[j].v[k]]=(f[i][t[j].v[k]]+f[i-1][j])%mod;55 ????????}56 ????ans1=1;57 ????for(int i=0;i<=cnt;++i)if(!t[i].s)ans2=(ans2+f[m][i])%mod;58 ????for(int i=1;i<=m;++i)ans1=ans1*26%mod;59 ????printf("%lld\n",(ans1-ans2+mod)%mod);60 ????return;61 }62 int main()63 {64 ????scanf("%d%d",&n,&m);65 ????for(int i=1;i<=n;++i)66 ????scanf("%s",s),build();67 ????getfail();68 ????work();69 ????return 0;70 }