1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 using namespace std;10 #define N 200001011 char s[25];12 struct Trie13 {14     int ch[N][26], num, cnt[N], id[N]; //空间尽量开大点15 16     void init()17     {18         memset(ch[0], 0, sizeof(ch[0]));19         num = 1;20     }21 22     void update(char *s, int index)23     {24         int u = 0;25         int len = strlen(s);26         for(int i = 0; i < len; i++) {27             int tmp = s[i] - ‘a‘;28             if(!ch[u][tmp]) {29                 memset(ch[num], 0, sizeof(ch[num]));30                 cnt[num] = 0;31                 id[num] = 0;32                 ch[u][tmp] = num++;33             }34             u = ch[u][tmp];35             if(id[u] != index) cnt[u]++;36             id[u] = index; //标记上一个是否是相同的串,如果相同不能重复计数37         }38     }39 40     int query(char *s)41     {42         int u = 0;43         int len = strlen(s);44         for(int i = 0; i < len; i++) {45             int tmp = s[i] - ‘a‘;46             if(!ch[u][tmp]) return 0;47             u = ch[u][tmp];48         }49         return cnt[u];50     }51 }trie;52 53 int main()54 {55     int n;56     scanf("%d", &n);57     trie.init();58     for(int i = 1; i <= n; i++) {59         scanf("%*c%s", s);60         int len = strlen(s);61         for(int j = 0; j < len; j++) {62             trie.update(s + j, i); //每一个串的以s[j]开头的子串都要插入63         }64     }65     scanf("%d", &n);66     for(int i = 0; i < n; i++) {67         scanf("%*c%s", s);68         printf("%d\n", trie.query(s));69     }70     return 0;71 }