JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。 ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？
输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。 这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A..Z 。
一个整数，表示可能的文章总数。只需要知道结果模10007的值。
裸的AC自动机上跑dp，合法的就是all-illegal。f[i][j]表示长度为i，在j节点的方案数。
1 #include<cstring> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<queue> 5 #include<vector> 6 7 using namespace std; 8 9 #define maxn 110 10 #define rhl (10007) 11 int n,m,f[maxn][maxn*60]; 12 char buf[maxn]; 13 queue <int> team; vector <int> son[maxn*60]; 14 struct trie 15 { 16 int next[maxn*60][26],fail[maxn*60],root,L; 17 bool end[maxn*60]; 18 19 inline int newnode() 20 { 21 memset(next[L],-1,sizeof(next[L])); 22 L++; return L - 1; 23 } 24 25 inline void init() 26 { 27 L = 0; root = newnode(); 28 } 29 30 inline void insert() 31 { 32 int len = strlen(buf),now = root; 33 for (int i = 0;i < len;++i) 34 { 35 if (next[now][buf[i] - ‘A‘] == -1) 36 next[now][buf[i] - ‘A‘] = newnode(); 37 now = next[now][buf[i] - ‘A‘]; 38 } 39 end[now] = true; 40 } 41 42 inline void build() 43 { 44 int now; 45 fail[root] = root; 46 for (int i = 0;i < 26;++i) 47 if (next[root][i] == -1) 48 next[root][i] = root; 49 else 50 fail[next[root][i]] = root,team.push(next[root][i]); 51 while (!team.empty()) 52 { 53 now = team.front(); team.pop(); 54 for (int i = 0;i < 26;++i) 55 if (next[now][i] == -1) 56 next[now][i] = next[fail[now]][i]; 57 else fail[next[now][i]] = next[fail[now]][i],team.push(next[now][i]); 58 } 59 } 60 61 inline void ready() 62 { 63 for (int i = 0;i < L;++i) 64 if (fail[i] != i) son[fail[i]].push_back(i); 65 int now; team.push(root); 66 while (!team.empty()) 67 { 68 now = team.front(); team.pop(); 69 int nn = son[now].size(); 70 for (int i = 0;i < nn;++i) 71 { 72 int v = son[now][i]; 73 team.push(v); 74 if (end[now]) end[v] = true; 75 } 76 } 77 } 78 79 inline int dp() 80 { 81 f[0][root] = 1; 82 for (int j = 0;j < m;++j) 83 { 84 for (int i = 0;i < L;++i) 85 { 86 if (end[i]) continue; 87 if (!f[j][i]) continue; 88 for (int k = 0;k < 26;++k) 89 { 90 if (end[next[i][k]]) continue; 91 f[j+1][next[i][k]] += f[j][i]; 92 while (f[j+1][next[i][k]] >= rhl) f[j+1][next[i][k]] -= rhl; 93 } 94 } 95 } 96 int res = 0; 97 for (int i = 0;i < L;++i) 98 if (!end[i]) 99 { 100 res += f[m][i]; 101 while (res >= rhl) res -= rhl; 102 } 103 int all = 1; 104 for (int i = 1;i <= m;++i) (all *= 26)%=rhl; 105 return all - res; 106 } 107 }ac; 108 109 int main() 110 { 111 freopen("1030.in","r",stdin); 112 freopen("1030.out","w",stdout); 113 scanf("%d %d\n",&n,&m); 114 ac.init(); 115 while (n--) 116 { 117 scanf("%s",buf); 118 ac.insert(); 119 } 120 ac.build(); 121 ac.ready(); 122 int ans = ac.dp(); printf("%d",(ans%rhl+rhl)%rhl); 123 fclose(stdin); fclose(stdout); 124 return 0; 125 }
原文：http://www.cnblogs.com/mmlz/p/4270914.html
