Trie模板 UVALive 3942 Remember the Word

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 
 5 const long long maxnode    = 4010*100;
 6 const long long SIGMA_SIZE = 26;
 7 const long long maxlen     = 100;
 8 const long long maxn       = 300010;
 9 const long long MOD        = 20071027;
10 
11 using namespace std;
12 
13 char s[maxn];
14 int f[maxn];
15 
16 struct Trie
17 {
18     int ch[maxnode][SIGMA_SIZE];
19     int val[maxnode];
20     int size;
21     Trie(){clear();}
22     void clear(){
23         size=1;
24         memset(ch[0],0,sizeof(ch[0]));
25         memset(val,0,sizeof(val));
26     }
27     int index(char t){return t-'a';};
28     int buildNewNode(int u){
29         memset(ch[size],0,sizeof(ch[size]));
30         val[size]=u;
31         return size++;
32     }
33     void insert(char *s){
34         int u = 0;
35         for(;*s;s++){
36             int c = index(*s);
37             if(!ch[u][c])
38                 ch[u][c]=buildNewNode(0);
39             u=ch[u][c];
40         }
41         val[u]=1;//val[u]=v
42     }
43     void find(int i,char *s){
44         int u=0,len=0;
45         for(;*s;s++){
46             int c = index(*s);
47             if(ch[u][c]){
48                 len++;
49                 u=ch[u][c];
50                 f[i+len]=(val[u]*f[i]+f[i+len])%MOD;
51                 //if(val[u]){find an end }
52             }
53             else
54                 break;
55         }
56 
57     }
58 };
59 
60 Trie trie;
61 
62 int main()
63 {
64     int CaseNum = 0;
65     while(scanf("%s",s)!=EOF){
66         int n,len=strlen(s);
67         memset(f,0,sizeof(f));f[0]=1;
68         trie.clear();
69 
70         scanf("%d",&n);
71         for(int i=0;i<n;i++){
72             char key[110];
73             scanf("%s",key);
74             trie.insert(key);
75         }
76 
77         for(int i=1;i<=len;i++)
78             trie.find(i-1,s+i-1);
79 
80         printf("Case %d: %d
",++CaseNum,f[len]);
81 
82     }
83     return 0;
84 }