1030: [JSOI2007]文本生成器

Time Limit: 1 Sec  

Memory Limit: 162 MB

Submit: 2635  

Solved: 1090

[ ][ ][ ]

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自己主动机上的dp

dp[0][i][j]表示到第i位，以第j个状态结束不符合条件的串的个数

dp[1][i][j]表示到第i位，以第j个状态结束符合条件的串的个数

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 6005;const int MOD = 10007;int que[N], fr, ta;struct ACM {	int cnt;	int nxt[N][26], sum[N], fail[N];	void init() {		for(int i = 1; i <= cnt; ++i) {			sum[i] = fail[i] = 0;			for(int j = 0; j < 26; ++j)				nxt[i][j] = 0;		}		cnt = 1;		for(int i = 0; i < 26; ++i) nxt[0][i] = 1;	}	void insert(string str) {		int now = 1;		int len = str.length();		for(int i = 0; i < len; ++i) {			if(nxt[now][str[i] - 'A'] == 0) nxt[now][str[i] - 'A'] = ++cnt;			now = nxt[now][str[i] - 'A'];		}		sum[now] = 1;	}	void build_fail() {		fr = ta = 0;		que[ta++] = 1;		fail[1] = 0;		while(fr != ta) {			int now = que[fr++];			for(int i = 0; i < 26; ++i) {				int x = nxt[now][i];				if(x == 0) continue;				int tmp = fail[now];				while(nxt[tmp][i] == 0) tmp = fail[tmp];				fail[x] = nxt[tmp][i];				que[ta++] = x;			}		}	}	void debug() {		for(int i = 1; i <= cnt; ++i) {			cout<
         <<": "<<"fail = "<
          
           <<" [ "; for(int j = 0; j < 26; ++j) { if(nxt[i][j]) cout<
           
            = 0 && pos < len) return false; } return true;}int main() { int n, m; cin>>n>>m; acm.init(); for(int i = 0; i < n; ++i) { cin>>str[i]; } sort(str, str + n); n = unique(str, str + n) - str; for(int i = 0; i < n; ++i) { if(ok(i, n)) acm.insert(str[i]); } acm.gao(n, m); return 0;}