题目大意：
给定n个给定的串，求有多少个串满足存在给定的串是这个串的子串。
思路：
直接计算存在的不太好算，考虑反面计数，计算有多少个串找不到匹配。
那么当我们把AC自动机给建出来之后，不难发现一个满足要求的串会一直在AC自动机上面跳并且到不了已经匹配上的节点，于是问题便转化成了有向图的路径计数。
考虑DP，记dp[i][j]表示走了i步走到了第j个节点，每一个点枚举下一个字符是什么，直接在AC自动机上转移即可。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)#define debug(x) cout<<#x<<"="<<x<<" "#define fi first#define se second#define mk make_pair#define pb push_backtypedef long long ll; using namespace std; void File(){ ???freopen("bzoj1030.in","r",stdin); ???freopen("bzoj1030.out","w",stdout);} template<typename T>void read(T &_){ ???_=0; T f=1; char c=getchar(); ???for(;!isdigit(c);c=getchar())if(c=='-')f=-1; ???for(;isdigit(c);c=getchar())_=(_<<1)+(_<<3)+(c^'0'); ???_*=f;} const int maxn=6000+10;const int mod=1e4+7;int n,m,dp[110][maxn];int ch[maxn][26],num[maxn],fail[maxn],cnt=1; void insert(char *s){ ???int len=strlen(s+1),u=1,c; ???REP(i,1,len){ ???????c=s[i]-'A'; ???????if(!ch[u][c])ch[u][c]=++cnt; ???????u=ch[u][c]; ???} ???++num[u];} void build_fail(){ ???int h=1,t=0,q[maxn]; ???fail[1]=1; ???REP(i,0,25){ ???????int v=ch[1][i]; ???????if(v)q[++t]=v; ???????if(v)fail[v]=1; ???????else ch[1][i]=1; ???} ???while(h<=t){ ???????int u=q[h++]; ???????REP(i,0,25){ ???????????int v=ch[u][i]; ???????????if(v)q[++t]=v; ???????????if(v){ ???????????????fail[v]=max(ch[fail[u]][i],1); ???????????????num[v]|=num[fail[v]]; ???????????} ???????????else ch[u][i]=max(ch[fail[u]][i],1); ???????} ???}} void ad(int &x,int y){x=(x+y)%mod;} void work(){ ???dp[1][1]=1; ???REP(i,1,m)REP(j,1,cnt)REP(k,0,25) ???????if(!num[ch[j][k]]) ???????????ad(dp[i+1][ch[j][k]],dp[i][j]); ???int ans=1; ???REP(i,1,m)ans=ans*26%mod; ???REP(i,1,cnt)ad(ans,-dp[m+1][i]); ???printf("%d\n",(ans+mod)%mod);} int main(){ ???//File(); ???char s[maxn]; ????read(n); read(m); ???REP(i,1,n){ ???????scanf("%s",s+1); ???????insert(s); ???} ????build_fail(); ????work(); ???//cout<<"÷"<<endl; ???return 0;}[bzoj1030][JSOI2007]文本生成器——AC自动机+动态规划
原文地址：https://www.cnblogs.com/ylsoi/p/10186792.html