1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <queue>  5 using namespace std;  6   7 #define MAXN  515*70  8 #define NXTN  256  9  10 bool visit[515]; 11 char str[3005]; 12 unsigned char buf[2050], src[3005]; 13  14 typedef struct { 15     int next[MAXN][NXTN], fail[MAXN], v[MAXN]; 16     int root, n; 17     void init() { 18         n = 0; 19         root = newNode(); 20     } 21     int newNode() { 22         for (int i=0; i<NXTN; ++i) 23             next[n][i] = -1; 24         v[n] = 0; 25         return n++; 26     } 27     void create(unsigned char s[], int len, int in) { 28         int i = 0, cur = root, tmp; 29  30         while (i < len) { 31             if (next[cur][s[i]] == -1) { 32                 tmp = newNode(); 33                 next[cur][s[i]] = tmp; 34             } 35             cur = next[cur][s[i]]; 36             ++i; 37         } 38         v[cur] = in; 39     } 40     void build() { 41         int i, cur; 42         queue<int> que; 43  44         fail[root] = root; 45         for (i=0; i<NXTN; ++i) { 46             if (next[root][i] == -1) { 47                 next[root][i] = root; 48             } else { 49                 fail[next[root][i]] = root; 50                 que.push(next[root][i]); 51             } 52         } 53  54         while (!que.empty()) { 55             cur = que.front(); 56             que.pop(); 57             for (i=0; i<NXTN; ++i) { 58                 if (next[cur][i] == -1) { 59                     next[cur][i] = next[fail[cur]][i]; 60                 } else { 61                     fail[next[cur][i]] = next[fail[cur]][i]; 62                     que.push(next[cur][i]); 63                 } 64             } 65         } 66     } 67     void query(unsigned char s[], int len) { 68         int i = 0, cur = root, tmp; 69  70         memset(visit, false, sizeof(visit)); 71         while (i < len) { 72             cur = next[cur][s[i]]; 73             tmp = cur; 74             while (tmp != root) { 75                 visit[v[tmp]] = true; 76                 tmp = fail[tmp]; 77             } 78             ++i; 79         } 80     } 81 } AC; 82  83 void output(int n) { 84     int ans = 0; 85     for (int i=1; i<=n; ++i) 86         if (visit[i]) 87             ++ans; 88     printf("%d\n", ans); 89 } 90  91 unsigned char getVal(char c) { 92     if (c>=‘A‘ && c<=‘Z‘) 93         return c - ‘A‘; 94     if (c>=‘a‘ && c<=‘z‘) 95         return c - ‘a‘ + 26; 96     if (c>=‘0‘ && c<=‘9‘) 97         return c - ‘0‘ + 52; 98     if (c == ‘+‘) return 62; 99     return 63;100 }101 102 int decode(unsigned char src[], int len) {103     int i, k = 0;104 105     for (i=0; i<len; i+=4) {106         buf[k++] = (src[i]<<2)+(src[i+1]>>4);107         if (i+2 < len)108             buf[k++] = (src[i+1]<<4) + (src[i+2]>>2);109         if (i+3 < len)110             buf[k++] = (src[i+2]<<6) + (src[i+3]);111     }112     return k;113 }114 115 AC ac;116 117 int main() {118     int i, j, l, n, m;119 120 121     while (scanf("%d", &n) != EOF) {122         ac.init();123         for (i=1; i<=n; ++i) {124             scanf("%s", str);125             for (j=0; str[j]&&str[j]!=‘=‘; ++j) {126                 src[j] = getVal(str[j]);127             }128             l = decode(src, j);129             ac.create(buf, l, i);130         }131         ac.build();132         scanf("%d", &m);133         while (m--) {134             scanf("%s", str);135             for (j=0; str[j]; ++j) {136                 if (str[j] == ‘=‘)137                     break;138                 src[j] = getVal(str[j]);139             }140             l = decode(src, j);141             ac.query(buf, l);142             output(n);143         }144         printf("\n");145     }146 147     return 0;148 }