Remember the Word

Since Jiejie can’t remember numbers clearly, he just uses sticks to help himself. Allowing for Jiejie’s

only 20071027 sticks, he can only record the remainders of the numbers divided by total amount of

sticks.

The problem is as follows: a word needs to be divided into small pieces in such a way that each

piece is from some given set of words. Given a word and the set of words, Jiejie should calculate the

number of ways the given word can be divided, using the words in the set.

Input

The input file contains multiple test cases. For each test case: the first line contains the given word

whose length is no more than 300 000.

The second line contains an integer S, 1 ≤ S ≤ 4000.

Each of the following S lines contains one word from the set. Each word will be at most 100

characters long. There will be no two identical words and all letters in the words will be lowercase.

There is a blank line between consecutive test cases.

You should proceed to the end of file.

Output

For each test case, output the number, as described above, from the task description modulo 20071027.

Sample Input

abcd

4

a

b

cd

ab

Sample Output

Case 1: 2

 

题意：

给出一个由S个不同单词组成的字典和一个长字符串。吧这个字符串分解成若干个单词的连接，有多少种方法。

题解：

　　大白

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long ll;int mod = 20071027;const int N = 300005;const int maxnode = 400005;struct Trie { int ch[maxnode][26],val[maxnode]; int siz; void trie_clear() {siz = 1, memset(ch[0],0,sizeof(ch[0]));} int idx (char c) { return c - 'a';} // 插入字符串s，附加信息为v。注意v必须非0，因为0代表“本结点不是单词结点” void trie_insert(const char *s,int v) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++) { int c= idx(s[i]); if(!ch[u][c]) { // 结点不存在 memset(ch[siz],0,sizeof(ch[siz])); val[siz] = 0; // 中间结点的附加信息为0 ch[u][c] = siz++; // 新建结点 } u = ch[u][c];// 往下走 } val[u] = v;// 字符串的最后一个字符的附加信息为v } void trie_find(const char *s, int len, vector
            
             & ans) { int u = 0; for(int i = 0; i < len; i++) { if(s[i] == '\0')break; int c= idx(s[i]); if(!ch[u][c]) break; u = ch[u][c]; if(val[u] != 0) ans.push_back(val[u]); } }};Trie P;char s[N], ss[N];int d[N],len[N],n;int solve() { P.trie_clear(); for(int i = 1; i <= n; i++) { scanf("%s", ss); len[i] = strlen(ss); P.trie_insert(ss,i); } memset(d,0,sizeof(d)); int L = strlen(s); d[L] = 1; for(int i = L-1; i >= 0; i--) { vector
             
               ans; P.trie_find(s+i,L-i,ans); for(int j = 0; j < ans.size(); j++) { d[i] = (d[i] + d[i+len[ans[j]]]) % mod; } } return d[0];}int main() { int T = 1; while(scanf("%s%d", s,&n)!=EOF) { printf("Case %d: %d\n",T++,solve()); } return 0;}