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
A
B
Sample Output
100
题解
AC自动机模板。动归转移方面好像有些题可转矩阵乘法加速。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define mod 10007
using namespace std;
int n,m,q[6002],f[102][6002],ans1,ans2=1;
int trie[6002][27],size=1,dg[6002],next[6002];
char ch[102];
void insert()
{
int i,w=1,k,l=strlen(ch);
for(i=0;i<l;i++)
{k=ch[i]-'A';
if(!trie[w][k]) trie[w][k]=++size;
w=trie[w][k];
}
dg[w]=1;
}
void init()
{
scanf("%d%d",&n,&m);
int i;
for(i=0;i<26;i++) trie[0][i]=1;
for(i=1;i<=n;i++)
{scanf("%s",ch); insert();}
}
void getfail()
{
int t=0,w=1,i,x,k;
q[0]=1; next[1]=0;//以1为根节点方便连接“失败指针”
while(t<w)
{x=q[t]; t++;
for(i=0;i<26;i++)
{if(!trie[x][i]) continue;
k=next[x];
while(!trie[k][i]) k=next[k];
next[trie[x][i]]=trie[k][i];
if(dg[trie[k][i]]) dg[trie[x][i]]=1;
q[w]=trie[x][i]; w++;
}
}
}
void dp(int x)
{
int i,j,k;
for(i=1;i<=size;i++)
{if(!dg[i]&&f[x-1][i])//因为不能走完一个单词，所以单词的结尾一定不可能走到
{for(j=0;j<26;j++)
{k=i;
while(!trie[k][j]) k=next[k];
f[x][trie[k][j]]+=f[x-1][i]; f[x][trie[k][j]]%=mod;
}
}
}
}
void work()
{
int i;
f[0][1]=1;
for(i=1;i<=m;i++) {dp(i); ans2=(ans2*26)%mod;}
for(i=1;i<=size;i++)
{if(!dg[i]) ans1=(ans1+f[m][i])%mod;}
printf("%d\n",(ans2-ans1+mod)%mod);
}
int main()
{
init(); getfail();
work();
return 0;
}