题意
给你n个串。问有多少长度为m的串使得这n个串至少在其中出现过一次。输出答案膜10007意义下的结果。
（n<=100,每个串的长度<=100）
题解
在AC自动机上跑DP。
用到一个容斥的思想，求至少出现过一次的次数就是，全部可能-一次都没出现的次数。
所以考虑dp，对于一个长度为i的串从i-1转移，i位置上的数必须不是n个串中某个串的结尾。
所以建立AC自动机，在上面跑。一个儿子从父亲转移时必须保证，儿子节点和儿子节点通过fail指针间接到达的点，都不是终止节点。
具体看代码。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 const int mod=10007; 9 const int N=7000;10 int n,m,tot,ans;11 char s[N];12 int dp[200][N];13 struct AC{14 ????int nxt[30],e,fail;15 }ac[N];16 void insert(char s[]){17 // ???cout<<"asfsfsdfsdfs"<<endl;18 ????int len=strlen(s);19 ????int now=0;20 ????for(int i=0;i<len;i++){21 ????????if(ac[now].nxt[s[i]-‘A‘]==0)ac[now].nxt[s[i]-‘A‘]=++tot;22 ????????now=ac[now].nxt[s[i]-‘A‘];23 ????}24 ????ac[now].e=1;25 }26 void get_fail(){27 ????queue<int>q;28 ????for(int i=0;i<=25;i++){29 ????????if(ac[0].nxt[i]){30 ????????// ???cout<<"sfsd"<<endl;31 ????????????q.push(ac[0].nxt[i]);32 ????????}33 ????}34 ????while(!q.empty()){35 ????????36 ????????int u=q.front();//cout<<u<<endl;37 ????????q.pop();38 ????????for(int i=0;i<=25;i++){39 ????????????if(ac[u].nxt[i]){40 ????????????????ac[ac[u].nxt[i]].fail=ac[ac[u].fail].nxt[i];41 ????????????????ac[ac[u].nxt[i]].e|=ac[ac[ac[u].fail].nxt[i]].e;42 ????????????????q.push(ac[u].nxt[i]);43 ????????????}44 ????????????else ac[u].nxt[i]=ac[ac[u].fail].nxt[i];45 ????????}46 ????}47 }48 int main(){49 ????scanf("%d%d",&n,&m);50 ????for(int i=1;i<=n;i++){51 ????????scanf("%s",s);52 ????????insert(s);53 ????}54 ????get_fail();55 ????dp[0][0]=1;56 ????for(int i=1;i<=m;i++)57 ????????for(int j=0;j<=tot;j++)58 ????????????for(int x=0;x<=25;x++){59 ????????????????if(ac[ac[j].nxt[x]].e==0)dp[i][ac[j].nxt[x]]=(dp[i][ac[j].nxt[x]]+dp[i-1][j])%mod;60 ????????????}61 ????int ans=1;62 ????for(int i=1;i<=m;i++){63 ????????ans*=26;64 ????????ans%=mod;65 ????}66 ????for(int i=0;i<=tot;i++){67 ????????ans-=dp[m][i];68 ????????ans=(ans+mod)%mod;69 ????}70 ????printf("%d",ans);71 ????return 0;72 }[JSOI2007]文本生成器（AC自动机+DP）
原文地址：https://www.cnblogs.com/Xu-daxia/p/9525060.html