#include <bits/stdc++.h>
using namespace std;
// 全局常量：
// 预估节点上界（保证所有输入字符串的总长度不超过 3e6 时足够）  
const int MAX_NODES = 3000005;  
// 字符映射大小： 'A'-'Z' (26) + 'a'-'z' (26) + '0'-'9' (10) = 62  
const int ALPHABET_SIZE = 62;

// 静态全局数组：用于存储字典树节点信息
// trie[node][c] 表示节点 node 的下标为 c 的子节点编号，0 表示不存在
static int trie[MAX_NODES][ALPHABET_SIZE];
// cntArr[node] 表示经过节点 node 的模式串数量（即有多少模式串以该节点为前缀）
static int cntArr[MAX_NODES];

// 全局节点编号，根节点固定为 0，后续新节点编号依次递增
int idx = 0;

// 用于记录本组测试数据中实际创建的节点编号（包括根节点 0），
// 在每组测试数据结束后只需将这些节点重置
vector<int> usedNodes;

// 将字符 x 映射成 0～ALPHABET_SIZE-1 的下标  
// 'A'-'Z' 映射到 [0,25]；'a'-'z' 映射到 [26,51]；'0'-'9' 映射到 [52,61]
int getNum(char x) {
    if (x >= 'A' && x <= 'Z')
        return x - 'A';
    else if (x >= 'a' && x <= 'z')
        return x - 'a' + 26;
    else // x 为数字
        return x - '0' + 52;
}

// 初始化字典树数据结构，每组测试数据调用一次
// 只重置上一次使用过的节点，避免遍历整个 MAX_NODES 数组
void initTrie() {
    // 如果是新数据组，先清空 usedNodes 数组，并保留根节点（0）
    usedNodes.clear();
    usedNodes.push_back(0);
    // 重置根节点的所有子节点为 0
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        trie[0][i] = 0;
    }
    cntArr[0] = 0;
    idx = 0;
}

// 插入字符串 str 到字典树中
// 每遍历一个字符，若对应子节点不存在，则创建新节点，记录到 usedNodes 中
// 并对经过的节点计数加 1
void insertStr(const string &str) {
    int cur = 0;
    for (char ch : str) {
        int c = getNum(ch);
        if (trie[cur][c] == 0) { 
            // 创建新节点
            trie[cur][c] = ++idx;
            usedNodes.push_back(idx);
            // 初始化新节点的子节点为 0
            for (int j = 0; j < ALPHABET_SIZE; j++) {
                trie[idx][j] = 0;
            }
            cntArr[idx] = 0;
        }
        cur = trie[cur][c];
        cntArr[cur]++; // 经过当前节点的模式串数量增加
    }
}

// 查询字符串 str 作为前缀出现的次数
// 沿着字典树遍历，若中途发现没有对应路径，则返回 0；否则返回最后节点的计数
int queryStr(const string &str) {
    int cur = 0;
    for (char ch : str) {
        int c = getNum(ch);
        if (trie[cur][c] == 0)
            return 0;
        cur = trie[cur][c];
    }
    return cntArr[cur];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;  // 数据组数
    cin >> T;
    while (T--) {
        int n, q;  // 模式串个数和查询次数
        cin >> n >> q;
        initTrie();  // 初始化字典树

        // 插入 n 个模式串
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            insertStr(s);
        }
        // 处理 q 个查询
        for (int i = 0; i < q; i++) {
            string s;
            cin >> s;
            cout << queryStr(s) << "\n";
        }
    }
    return 0;
}

三.字典树的操作 1.映射字符

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

2.插入字符串

void insert(char str[])
{
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}

3.查询操作

int find(char str[])
{
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}