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 考慮用總方案數-不合法方案數用f[i][j]表示長度為i位于Tire樹中j號節點時所有不合法的方案數。 若當前處于j號節點，且Next[j][k]不是一個字符串的結尾，那么就可以由j號節點向Next[j][k]轉移，即f[i][Next[j][k]]=f[i][Next[j][k]]+f[i-1][j] #include <bits/stdc++.h> #define ll long long using namespace std; const int p=10007; const int N=150; const int M=1e4+50; int n,m; char s[N]; struct acmach {int Next[M][26],Fail[M],End[M],f[N][M];int root,L;int newnode(){for (int i=0;i<26;i++) Next[L][i]=-1;End[L]=0;return L++;}void init(){L=0;root=newnode();}void Insert(char s[]){int len=strlen(s);int now=root;for (int i=0;i<len;i++){if (Next[now][s[i]-'A']==-1)Next[now][s[i]-'A']=newnode();now=Next[now][s[i]-'A'];}End[now]++;}void build(){queue<int>q;Fail[root]=root; //當前節點now的失敗指針指向的地方for (int i=0;i<26;i++)if (Next[root][i]==-1) Next[root][i]=root; //下一個字母為i+'a'的節點的下標為Next[now][i]else{Fail[Next[root][i]]=root;q.push(Next[root][i]);}while (!q.empty()){int now=q.front(); q.pop();for (int i=0;i<26;i++)if (Next[now][i]==-1) Next[now][i]=Next[Fail[now]][i]; //指向當前節點fail指針的這個子節點else{Fail[Next[now][i]]=Next[Fail[now]][i]; //這個節點的失敗指針指向(((他父親節點)的失敗指針所指向的那個節點)的下一個節點) q.push(Next[now][i]);}End[now]+=End[Fail[now]];}}int query(){f[0][0]=1; //f[i][j]為當前長度為i的字符串處于Trie樹中的第j號結點所具有的方案數。for (int i=1;i<=m;i++)for (int j=0;j<L;j++){if (End[j]) continue;for (int k=0;k<26;k++){if(End[Next[j][k]]) continue;f[i][Next[j][k]]=(f[i][Next[j][k]]+f[i-1][j])%p;}}int ret=1,sum=0;for (int i=1;i<=m;i++) ret=ret*26%p;for (int i=0;i<L;i++) sum=(sum+f[m][i])%p;return (ret-sum+p)%p;} }ac; int main() {ac.init();scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%s",s);ac.Insert(s);}ac.build();printf("%d\n",ac.query());return 0; } /* 2 2 A B */ View Code

?

轉載于:https://www.cnblogs.com/tetew/p/11262425.html

總結

以上是生活随笔為你收集整理的BZOJ1030: [JSOI2007]文本生成器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。