题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1030
求至少有一个单词的文本串不太好求，所以转化成求所有情况减去没有一个单词的文本串；
没有一个单词的文本串可以用AC自动机+DP求，设 f[i][j] 表示文本串长度为 i ，当前 Trie 树上节点为 j 的方案数；
则 f[i][j] 可以转到仍然不包含单词的它的儿子的方案数中，同时文本串长度+1；
所以需要在 getfail 时把单词结尾的属性也转移一下，因为 fail 是单词结尾的话，自己也一定有一个后缀是单词结尾，也就是自己这里也包含单词了；
最后统计答案就是所有的 f[m][i] 的和，其中 i 可以是 Trie 树上任意一个点。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;int const mod=10007;int n,m,f[105][6005],cnt,ans;char s[105];queue<int>q;struct N{int son[30],fail,end;}t[6005];void build(){ ???int l=strlen(s),nw=0; ???for(int i=0;i<l;i++) ???{ ???????if(!t[nw].son[s[i]-‘A‘])t[nw].son[s[i]-‘A‘]=++cnt; ???????nw=t[nw].son[s[i]-‘A‘]; ???} ???t[nw].end=1;}void getfail(){ ???t[0].fail=0; ???for(int i=0;i<26;i++) ???????if(t[0].son[i]) ???????{ ???????????t[t[0].son[i]].fail=0; ???????????q.push(t[0].son[i]); ???????} ???while(q.size()) ???{ ???????int x=q.front(); q.pop(); ???????for(int i=0;i<26;i++) ???????{ ???????????if(t[x].son[i]) ???????????{ ???????????????t[t[x].son[i]].fail=t[t[x].fail].son[i];// ???????????????t[t[x].son[i]].end|=t[t[t[x].son[i]].fail].end; ???????????????q.push(t[x].son[i]); ???????????} ???????????else t[x].son[i]=t[t[x].fail].son[i]; ???????} ???????if(t[t[x].fail].end)t[x].end=1; ???} ???}int main(){ ???scanf("%d%d",&n,&m); ???for(int i=1;i<=n;i++) ???{ ???????cin>>s; ???????build(); ???} ???getfail(); ???f[0][0]=1;//! ???for(int i=0;i<m;i++) ???????for(int nw=0;nw<=cnt;nw++) ???????{ ???????????if(t[nw].end||!f[i][nw])continue;// ???????????for(int j=0;j<26;j++) ???????????{ ???????????????int x=t[nw].son[j]; ???????????????(f[i+1][x]+=f[i][nw])%=mod; ???????????} ???????} ???ans=1; ???for(int i=1;i<=m;i++) (ans*=26)%=mod; ???for(int i=0;i<=cnt;i++) ????????if(t[i].end==0)ans=((ans-f[m][i])%mod+mod)%mod; //end=0! ???printf("%d",ans); ???return 0;}bzoj1030 [JSOI2007]文本生成器——AC自动机+DP
原文地址：https://www.cnblogs.com/Zinn/p/9325671.html