求助字典树，48pts。

rt，wa

#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;
}