傳送門
題面：
1030: [JSOI2007]文本生成器
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 6094 Solved: 2580
[Submit][Status][Discuss]
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自動機去維護。
不難發現，如果沒有限制，一個長度為m的字元串最多可能構成 26^m種字元串。而如果加上限制條件，我們直接去算可行的方案就相當困難。但是我們發現，不可行的方案相對來說比較好求，隻需要剔除完整的字元串的方案數即可。是以我們可以優先考慮西安求出不可行的方案數res，并用 26^m-res即為需要求的可行的結果。
而對于不可行的方案數，我們可以用dp記錄方案數去求解。我們設dp[i][j]為目前長度為i的字元串處于Trie樹中的第j号結點所具有的方案數。
根據AC自動機next數組的性質，我們不難發現，長度為i+1，位于第j個結點的方案數可以轉移到長度為i，位于第next[j][k]結點的方案數，即dp[i+1][j]=dp[i+1][j]+dp[i][next[j][k]]。而當我們周遊到第j 個結點時發現它可以作為終止結點，我們就跳過該結點，此時就可以求出不符合條件（湊不出完整字元串）的方案數了。
代碼：
#include <bits/stdc++.h>
#define maxn 105
using namespace std;
int dp[maxn][7000];
char s[500];
const int mod=10007;
int n,m;
struct Trie{
int next[10000][26],fail[10000],End[10000],id,root;
int newnode(){
for(int i=0;i<26;i++){
next[id][i]=-1;
}
End[id]=0;
return id++;
}
void init(){
id=0;
root=newnode();
}
void Insert(char *str){
int len=strlen(str);
int now=root;
for(int i=0;i<len;i++){
if(next[now][str[i]-'A']==-1){
next[now][str[i]-'A']=newnode();
}
now=next[now][str[i]-'A'];
}
End[now]=1;
}
void build(){
queue<int>que;
fail[root]=root;
for(int i=0;i<26;i++){
if(next[root][i]==-1){
next[root][i]=root;
}
else{
fail[next[root][i]]=root;
que.push(next[root][i]);
}
}
while(!que.empty()){
int now=que.front();
que.pop();
for(int i=0;i<26;i++){
if(next[now][i]==-1){
next[now][i]=next[fail[now]][i];
}
else{
fail[next[now][i]]=next[fail[now]][i];
que.push(next[now][i]);
}
}
End[now]|=End[fail[now]];//終點标志也需要轉移
}
}
}ac;
int powmod(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
void solve(){
dp[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<=ac.id;j++){
if(ac.End[j]) continue;//如果目前位為某一個串的終點
for(int k=0;k<26;k++){
if(ac.End[ac.next[j][k]]) continue;
dp[i][ac.next[j][k]]=(dp[i][ac.next[j][k]]+dp[i-1][j])%mod;
}
}
}
int res=0;
for(int i=0;i<=ac.id;i++){
res=(res+dp[m][i])%mod;
}
cout<<(powmod(26,m)-res+mod)%mod<<endl;
}
int main()
{
scanf("%d%d",&n,&m);
ac.init();
while(n--){
scanf("%s",s);
ac.Insert(s);
}
ac.build();
solve();
}