做到了AC自动机的题目，复习了一下AC自动机，学习了黄学长代码，这个题呢，我们可以模拟在AC自动机上的操作，dp数组f[i][j]表示前i个字符，我们在AC自动机上处在j号节点的方案数。
我们可以计算不符合条件的方案数，转移的时候不在有标记的节点转移就行了。—— by VANE
#include<bits/stdc++.h>using namespace std;const int N=6005;struct node{ ???int son[26],danger,fail;}ch[N];int n,m,f[105][6005],tot=1;const int mod=10007;char t[105];void insert(char s[]){ ???int now=1,len=strlen(s); ???for(int i=0;i<len;++i) ???{ ???????int w=s[i]-‘A‘; ???????if(ch[now].son[w]) now=ch[now].son[w]; ???????else now=ch[now].son[w]=++tot; ???} ???ch[now].danger=1;}void acmach(){ ???queue<int> q; ???q.push(1);ch[1].fail=0; ???while(!q.empty()) ???{ ???????int u=q.front();q.pop(); ???????for(int i=0;i<26;++i) ???????{ ???????????if(!ch[u].son[i]) continue; ???????????int v=ch[u].fail; ???????????while(!ch[v].son[i]) v=ch[v].fail; ???????????ch[ch[u].son[i]].fail=ch[v].son[i]; ???????????if(ch[ch[v].son[i]].danger) ch[ch[u].son[i]].danger=1; ???????????q.push(ch[u].son[i]); ???????} ???}}void dp(int x){ ???for(int i=1;i<=tot;++i) ???{ ???????if(ch[i].danger||!f[x-1][i]) continue; ???????for(int j=0;j<26;++j) ???????{ ???????????int k=i; ???????????while(!ch[k].son[j]) k=ch[k].fail; ???????????????????????f[x][ch[k].son[j]]=(f[x][ch[k].son[j]]+f[x-1][i])%mod; ???????} ???}}int main(){ ???scanf("%d%d",&n,&m); ???for(int i=0;i<26;++i) ch[0].son[i]=1; ???for(int i=1;i<=n;++i) ???{ ???????scanf("%s",t); ???????insert(t); ???} ???acmach(); ???f[0][1]=1; ???for(int i=1;i<=m;++i) dp(i); ???int sum=1; ???for(int i=1;i<=m;++i) sum=sum*26%mod; ???for(int i=1;i<=tot;++i) ???if(!ch[i].danger) sum=(sum-f[m][i]+mod)%mod; ???cout<<sum;}BZOJ【bzoj1030】[JSOI2007]文本生成器（AC自动机）
原文地址：https://www.cnblogs.com/nbwzyzngyl/p/8318912.html