bzoj1030 [JSOI2007]文本生成器

本文主要是介绍bzoj1030 [JSOI2007]文本生成器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
Description
　　JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？
Input
　　输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A..Z
Output
　　一个整数，表示可能的文章总数。只需要知道结果模10007的值。
Sample Input
2 2
A
B
Sample Output
100

题解

看到有字符串的题目首先想到的就是能不能用AC自动机，但是这道题要求出现至少一个字符串的方案数，如果每次都判断是否有一个字符串或者它的一个前缀在生成串中出现过几乎是不可能完成的事情，所以要转化一下思路，变成求不合法的字符串的个数，然后用26的m次方减就好了。这样的题几乎都是dp，所以我们就可以尝试推dp方程了。
如果一个字符串在文本串中出现过，那么如果在AC自动机上看，一定是到达了某个打过结束标记的节点。为了防止这种情况的发生，如果我们用f[i][j]表示在生成的文本串中进行到第i个位置，在AC自动机上匹配到第j个位置，那么只要我们不用带有结束标记的节点更新别的节点就好了。这样dp方程就可以推出来了。
这道题有几个需要注意的地方：一开始要将0号节点的所有儿子都赋为非0的值，否则会出现儿子更新0号节点的情况；还有就是在建立失配指针的时候，如果一个节点的Fail指针指向的节点有结束标记，那么这个点也必须有结束标记，否则就有可能出现某个给定的单词成为某个单词的后缀的情况。

CODE：

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int M=1e4+7;
struct AC
{int ch[26];int fail;bool isend;
}a[10000];
char s[101];
int f[105][10005];
int n,m,tot,ans;
inline void insert()
{int len=strlen(s),now=0;for(int i=0;i<len;i++){if(!a[now].ch[s[i]-'A']) a[now].ch[s[i]-'A']=++tot;now=a[now].ch[s[i]-'A'];}a[now].isend=1;
}
inline void makefail()
{queue<int>q;for(int i=0;i<26;i++)if(a[0].ch[i]) q.push(a[0].ch[i]);while(!q.empty()){int tmp=q.front();q.pop();for(int i=0;i<26;i++){if(!a[tmp].ch[i]){a[tmp].ch[i]=a[a[tmp].fail].ch[i];continue;}a[a[tmp].ch[i]].fail=a[a[tmp].fail].ch[i];if(a[a[a[tmp].ch[i]].fail].isend) a[a[tmp].ch[i]].isend=1;q.push(a[tmp].ch[i]);}}
}
inline int pow(int a,int b)
{int ans=1;for(;b;b>>=1,a=(1ll*a*a)%M)if(b&1) ans=(1ll*ans*a)%M;return ans;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",s),insert();for(int i=0;i<26;i++)if(!a[0].ch[i]) a[0].ch[i]=++tot;makefail();f[0][0]=1;for(int i=1;i<=m;i++)for(int j=0;j<=tot;j++)if(!a[j].isend)for(int k=0;k<26;k++)f[i][a[j].ch[k]]=(f[i][a[j].ch[k]]+f[i-1][j])%M;ans=pow(26,m);for(int i=1;i<=tot;i++)if(!a[i].isend) ans=(ans-f[m][i]+M)%M;printf("%d",ans);return 0;
}