1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分256秒  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 #include<queue> 25 #define LL long long 26 #define maxn 512*65 27 using namespace std; 28 int hs[515]; 29 struct Trie 30 { 31     int next[maxn][256],fail[maxn],end[maxn]; 32     int root, L; 33     int newnode() 34     { 35         memset(next[L],-1,sizeof(next[L])); 36         end[L++] = 0 ; 37         return L-1; 38     } 39     void init() 40     { 41         L = 0 ;  42         root = newnode(); 43     } 44     void insert(int buf[],int len,int K) 45     { 46         int now = root; 47         for(int i = 0 ;i < len ;i ++) 48         { 49             if(next[now][buf[i]] ==  -1) 50             { 51                 next[now][buf[i]] = newnode(); 52             } 53             now = next[now][buf[i]]; 54         } 55         end[now] = K; 56     } 57     void build() 58     { 59         queue<int> Q; 60         fail[root] = root;  61         for(int i = 0;i < 256;i ++) 62         { 63             if(next[root][i] == -1) 64             { 65                 next[root][i] = root;  //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。     66             }else{ 67                 fail[next[root][i]] = root; 68                 Q.push(next[root][i]); 69             } 70         } 71         while(!Q.empty()) 72         { 73             int now = Q.front(); 74             Q.pop(); 75             for(int i = 0 ;i < 256;i ++) 76             { 77                 if(next[now][i] == -1) 78                     next[now][i] =  next[fail[now]][i];  79                 else{ 80                     fail[next[now][i]] = next[fail[now]][i]; 81                     Q.push(next[now][i]); 82                 } 83             } 84         } 85     } 86     void query(int buf[],int len) 87     { 88         int now = root ;  89         for(int  i = 0 ;i < len;i ++) 90         { 91             now = next[now][buf[i]]; 92             int temp = now ;  93             while(temp != root) 94             { 95                 if(end[temp]) 96                 { 97                     hs[end[temp]] = 1; 98                 } 99                 temp = fail[temp];100             }101         }102     }103 };104 char buf[3058];105 int  temp[3058];106 Trie ac;107 int cbit(char c)108 {109     if(c >= ‘A‘ && c <= ‘Z‘) 110         return c -‘A‘;111     if(c >= ‘a‘ && c <= ‘z‘)112         return c -‘a‘ + 26;113     if(c >= ‘0‘ && c <= ‘z‘)114         return c -‘0‘ + 52;115     if(c == ‘+‘)116         return 62;117     else if(c == ‘/‘)return 63;118 }119 void debug(int x)120 {121     printf("%d\n",x);122     for(int  i = 0 ;i < x; i ++)123         printf("%c",temp[i]);124     printf("\n");125 }126 int lt = 0;127 void change(){128 129     int len = strlen(buf);130     int t = 0;  131     int ln = 0 ;132     int tt;133     lt = 0;134     for(int i = 0 ;i < len;i ++)135     {136         if(buf[i] != ‘=‘) 137         {138             if(buf[i] >= ‘A‘ && buf[i] <= ‘Z‘) 139                 tt =  buf[i] -‘A‘;140             else if(buf[i] >= ‘a‘ && buf[i] <= ‘z‘)141                 tt = buf[i]-‘a‘ + 26;142             else if(buf[i] >= ‘0‘ && buf[i] <= ‘z‘)143                 tt= buf[i] -‘0‘ + 52;144             else if(buf[i] == ‘+‘)145                 tt = 62;146             else if(buf[i] == ‘/‘)tt = 63;147             if(6 < 8 - t)148             {149                 ln += (tt << (8-t-6));150                 t += 6;151             }else{152                 ln += (tt >> (6-8+t));153                 temp[lt++] = ln;154                 ln = (tt&((1<<(6-8+t)) -1)) << (8-(6-8+t));155                 t = (6-8+t);156             }157         }158     }159     //printf("%d %d\n",lt,rlen);160 }161 162 int main(){163     int n;164     while(scanf("%d",&n) != EOF)165     {166         ac.init();167         for(int i =1 ;i <= n;i ++)168         {169             scanf("%s",buf);170             change();171             ac.insert(temp,lt,i); 172             // debug(lt);173         }174         ac.build();175         int m; 176         scanf("%d",&m);177         for(int i = 1;i <= m;i ++)178         {179             memset(hs,0,sizeof(hs));180             scanf("%s",buf);181             change();182             // debug(lt);183             int ans = 0; 184             ac.query(temp,lt);185             for(int i = 1;i <= n;i ++)186                 if(hs[i])187                 {188                     ans ++ ;189                 }190             printf("%d\n",ans);191         }192         printf("\n");193     }194     return 0;195 }