UVA-3942 Remember the Word

UVALive - 3942

Remember the Word

Neal is very curious about combinatorial problems, and now here comes a problem about words. Knowing that Ray has a photographic memory and this may not trouble him, Neal gives it to Jiejie. 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个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接(单词可以重复使用)，有多少种方法？比如，有4个单词a，b，cd，ab，则abcd有2种分解方法：a+b+cd和ab+cd
输入：
输入包含多组数据。每组数据第一行为小写字母组成的待分解字符串，长度L不超过300000。第二行为单词个数S(S<=4000)。以下S行每行为一个单词，由不超过100个小写字母组成。输入结束的标志为文件结束符(EOF)

#include<cstdio>
#include<cstring>
#define MOD 20071027
#define idx(c)  c-'a'
int size, trie[400000][26];//size:dynamic_point_number, trie:dynamic_point
bool val[400000];//mark if trie tree's point is a word_last
char strp[300010];//given long_word
int dp[300010];//dp[i]means from 0 to i ,how many case can be gather as it
void init(int x){val[x] = 0;memset(trie[x], 0, sizeof(trie[x]));}
void insert(char str[]){
  int u=0;
    for(int i=0;str[i];++i){int num=idx(str[i]);//mark num as int(it)
        if(!trie[u][num])init(size),trie[u][num]=size++;
        //if has not been visited
        //make it initialization and push it to trie[u]
        //at the same time renew the dynamic_point_number
        u=trie[u][num];}//-> at the next point
    val[u] = true;}//it's a word_last ,mark it true
void dynamic(int cs){
   memset(dp,0,sizeof(dp));dp[0]=1;int i;//initialization
    for(i=0;strp[i];++i){int u=0;
        for(int j=i;strp[j];++j){
            int num=idx(strp[j]);//mark num as int(it)
            if(!trie[u][num])break;//if has not been marked 
            //just don't have this word in the given words
            //just break
            u=trie[u][num];//-> at the next point
            if(val[u])dp[j+1]=(dp[j+1]+dp[i])%MOD;//dp_formula
            //if it is a word_last ,just renew the next point as the dp_formula
        }
    }//if finish_found ,just break
    printf("Case %d: %d
", cs, dp[i]);//printf 
}
int main(){int s;char str[110];
    for(int cs=1;~scanf("%s",strp);++cs){
        init(0);//initialization the dinamic_point
        size=1;//initialization the size
        scanf("%d",&s);//ciner the given parts's size
        while(s--)scanf("%s",str),insert(str);//then cin the parts,and give it to the  str_tree
        dynamic(cs);//pass the case to the function,against every group of data 
    }return 0;}

the program is just above,program is the best language