求助字典树，48pts。

#include <bits/stdc++.h>
using namespace std;

const int _ = 3e6 + 10;

int trie[_][100];
int cnt[int(1e5) + 10];
// cnt 存的是有多少个前缀。

int idx;

int getsum(char x) {
	if ('A' <= x && x <= 'Z') return x - 'A';
	else if ('a' <= x && x <= 'z') return x - 'a' + 26;
	else return x - '0' + 52;
}

// 基本操作：插入，查询；
// 扩展操作：查询是否是其他单词的前缀，有多少个前缀。

void insert(string s) {
	int p = 0;
	for (auto ch : s) {
		int k = getsum(ch);
		// trie 里面存的是索引

		if (!trie[p][k]) // 查找不到索引
			trie[p][k] = ++idx; // 链式前向星式创建

		p = trie[p][k];
		cnt[p]++; // 访问到这个索引，索引前缀++
	}
}

int find(string s) {
	int p = 0;

	for (auto ch : s) {
		int k = getsum(ch);
		// 访问到不存在的索引
		if (!trie[p][k]) return false; // 没匹配到末尾就没了
		p = trie[p][k]; // 继续下一个索引

	}
	return cnt[p];
}

int main() {
	int T;
	cin >> T;

	while (T--) {
		for (int i = 0; i <= idx; ++i)
			for (int j = 0; j <= 122; ++j)
				trie[i][j] = 0;
		for (int i = 0; i <= idx; ++i)
			cnt[i] = 0;
		idx = 0;
		int n, q;
		cin >> n >> q;
		while (n--) {
			string s;
			cin >> s;
			insert(s);
		}
		while (q--) {
			string s;
			cin >> s;
			cout << find(s) << endl;
		}
	}

	return 0;
}