F06 字典树(Trie)

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6+10;
char str[N];
int id, ch[N][65], ed[N];
int ys[150];
void ins(char s[]) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int j = ys[s[i]];
        if (ch[p][j] == 0) ch[p][j] = ++id;
        p = ch[p][j];
        ed[p]++;
    }
}
int query(char s[]) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int j = ys[s[i]];
        if (ch[p][j] == 0) return 0;
        p = ch[p][j];
    }
    return ed[p];
}
int main() {
	int T; scanf("%d", &T);
	id = 0; memset(ch, 0, sizeof(ch)); memset(ed, 0, sizeof(ed));
	for(char i = 'A'; i <= 'Z'; i++) ys[i] = i - 'A';
	for(char i = 'a'; i <= 'z'; i++) ys[i] = i - 'a' + 26;
	for(char i = '0'; i <= '9'; i++) ys[i] = i - '0' + 52;
	while (T--) {
		int n, m; scanf("%d%d", &n, &m);
		for(int i = 0;i<=id;i++) memset(ch[i], 0, sizeof(ch[i]));
		for(int i = 0;i<=id;i++) ed[i] = 0;
		id=0;
		for (int i = 1; i <= n; i++) scanf("%s", str), ins(str);

		for (int i = 1; i <= m; i++) {
			scanf("%s", str);
			printf("%d\n", query(str));
		}
	}
    return 0;
}