1 // File Name: h.cpp  2 // Author: darkdream  3 // Created Time: 2014年10月18日 星期六 11时35分02秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 //#define debug 26 #ifdef debug 27  28 #endif 29 using namespace std; 30 char str[6000005]; 31 char str1[6000005]; 32 int len;  33 int sp; 34 int change(char c) 35 { 36    if(c >= ‘a‘ && c <= ‘z‘) 37        return c- ‘a‘; 38    if(c >= ‘A‘ && c <= ‘Z‘) 39        return c - ‘A‘ + 26; 40    if(c >= ‘0‘ && c <= ‘9‘) 41        return c - ‘0‘ + 52; 42 } 43 struct node{ 44     int ne[63]; 45     int sub; 46     int iss; 47     int isend; 48     int be; 49     int en; 50 }N[220000]; 51 int LN,LT; 52 struct Trie{ 53     int newnode() 54     { 55         LN ++; 56         memset(N[LN].ne,-1,sizeof(N[LN].ne)); 57         N[LN].sub = -1; 58         N[LN].isend = 0 ; 59         N[LN].iss = 0 ;  60         N[LN].be = 0 ;  61         N[LN].en = 0 ;  62         return LN; 63     } 64     int root ;  65     void init() 66     { 67        root = newnode(); 68     } 69     int newTrie(Trie T[]) 70     { 71        LT ++; 72        T[LT].init(); 73        return LT; 74     } 75     void insert(Trie T[]) 76     { 77       //struct node *now = root; 78       int be = sp; 79 #ifdef debug 80               printf("%c%c%c\n",str[sp-1],str[sp],str[sp+1]); 81 #endif 82       while(be < len) 83       { 84           //printf("*******"); 85           if(str[be+1] == ‘}‘) 86           { 87             sp = be + 1; 88             return; 89           } 90           int i ; 91            92           be = be + 3; 93  94           if(str[be-1] == ‘}‘)  95           { 96             sp = be-1; 97             return; 98           } 99           if(be + 2 >= len)100           {101               return;102           }103           int now = root;104           for(i = be ;str[i] !=‘"‘;i ++)105           {106 #ifdef debug107               printf("%c",str[i]);108 #endif109               int tt = change(str[i]);110 111               if(N[now].ne[tt] == -1)112               {113                   N[now].ne[tt]= newnode();114               }115               now = N[now].ne[tt];116           }117           N[now].isend = 1;118           //printf("%c\n",str[i+2]);119           if(str[i+2] == ‘"‘)120           {121              N[now].be = i + 2;122              N[now].iss = 1; 123              int j = i + 3;   124              while(str[j] != ‘"‘)125              {126                j++ ; 127              }128              N[now].en = j;129              be = j; 130           }else{131             sp = i + 1;132             N[now].be = i + 2;133             N[now].sub = newTrie(T);134             T[N[now].sub].insert(T);135             be = sp;136             N[now].en = be;137           }138 #ifdef debug139           printf("\n%d %d\n",N[now].be,N[now].en);140          /*   for(int i = now->be ;i <= now->en;i ++)141                 printf("%c",str[i]);142             printf("\n");*/143 #endif144       }145       sp = be;146     }147     148 149     void query(Trie T[])150     {151     //    debug(root);152         int now = root;153         int i ;154 #ifdef debug155               printf("%d %c\n",sp,str1[sp]);156 #endif157         for(i = sp;str1[i] != ‘"‘  ;i ++)158         {159 #ifdef debug160              printf("%c",str1[i]);161 #endif162             int tt = change(str1[i]);163             if(N[now].ne[tt] != -1)164             {165                 now =N[now].ne[tt];    166             }else {167                 //printf("%d\n",i);168                 printf("Error!\n");169                 return;170             }171         }  172 #ifdef debug173         printf("\n**********8\n");174 #endif175         sp = i + 3; 176         if(N[now].isend == 0)177         { 178             printf("Error!\n");179             return;180         }181         if(sp >= len)182         {183             //printf("%d %d\n",now->be,now->en);184             for(int i = N[now].be ;i <= N[now].en;i ++)185                 printf("%c",str[i]);186             printf("\n");187         }else{188             if(N[now].sub == -1)189             {190                 printf("Error!\n");191                 return;192             }193             T[N[now].sub].query(T);194         }195     }196 }T[11005];197 //struct Trie T[11005];198 int main(){199     //freopen("test.in","r",stdin);200     int t; 201     scanf("%d",&t);202     int kt =  0 ; 203     while(t--)204     {205       memset(T,0,sizeof(T));206       memset(N,0,sizeof(N));207       scanf("%s",str);208       len = strlen(str);209       sp = -1;210       LN = 0;211       LT = 0;212       T[0].init();213       T[0].insert(T);214       int q; 215       scanf("%d",&q);216       for(int i = 1;i <= q;i ++)217       {218          scanf("%s",str1);219          sp = 1; 220          len = strlen(str1);221          T[0].query(T);222       }223     }224 return 0;225 }