1 #include<stdio.h>  2 #include<algorithm>  3 #include<stdlib.h>  4 #include<queue>  5 #include<iostream>  6 #include<string.h>  7 #include<math.h>  8 using namespace std;  9 typedef long long LL; 10 struct node 11 { 12     node *p[26]; 13     bool flag; 14     node() 15     { 16         memset(p,0,sizeof(p)); 17         flag = false; 18     } 19 }; 20 char str[300005]; 21 char ans[300]; 22 char bns[300]; 23 node *head; 24 void in(char *c,int l); 25 void ask(char *c,int k,int l); 26 LL dp[300005]; 27 const LL mod = 20071027; 28 void fr(node *q); 29 int main(void) 30 { 31     int i,j; 32     int __ca = 0; 33     while(scanf("%s",str)!=EOF) 34     { 35         int l = strlen(str); 36         int n; 37         scanf("%d",&n); 38         head = new node(); 39         while(n--) 40         { 41             scanf("%s",ans); 42             int k = strlen(ans); 43             in(ans,k); 44         } 45         memset(dp,0,sizeof(dp)); 46         dp[0] = 1; 47         for(i = 0; i < l; i++) 48         { 49             int x = max(0,i-100); 50             int v = 0; 51             for(j = i; j >= x; j--) 52             { 53                 bns[v++] = str[j]; 54             } 55             bns[v] = ‘\0‘; 56             ask(bns,i+1,v); 57         } 58         fr(head); 59         printf("Case %d: ",++__ca); 60         printf("%lld\n",dp[l]); 61     } 62     return 0; 63 } 64 void in(char *c,int l) 65 { 66     int i,j; 67     node *root = head; 68     for(i = l-1; i >=0; i--) 69     { 70         int x = c[i]-‘a‘; 71         if(root->p[x]==NULL) 72         { 73             root->p[x] = new node(); 74         } 75         root = root->p[x]; 76     } 77     root->flag = true; 78 } 79 void ask(char *c,int k,int l) 80 { 81     int i,j; 82     node *root = head; 83     for(i = 0; i < l; i++) 84     { 85         int x = c[i]-‘a‘; 86         if(root->p[x]==NULL) 87         { 88             return ; 89         } 90         else if(root->p[x]->flag) 91         { 92             dp[k] = dp[k] + dp[k-i-1]; 93             dp[k]%=mod; 94         } 95         root = root->p[x]; 96     } 97 } 98 void fr(node *q) 99 {100     int i,j;101     for(i = 0; i < 26; i++)102     {103         if(q->p[i])104         {105             fr(q->p[i]);106         }107     }108     free(q);109 }