字典树

#include<bits/stdc++.h>
#define maxn 3000005
using namespace std;
int n,q,id;
int trie[maxn][65],cnt[maxn];
char str[maxn];

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

void build(char a[])
{
	int p = 0;
	int len = strlen(a);
	for(int i = 0;i < len;i++)
	{
		int x = getnum(a[i]);//索引
		if(trie[p][x] == 0)
			trie[p][x] = ++id;//如果子节点不存在，则创造一个新的节点 
		p = trie[p][x];//移动到下一个节点 
		cnt[p]++;//字母出现的次数++ 
	}
	//cnt[p]++;//单词出现的次数++  
}

int find(char s[])
{
	int p = 0,len = strlen(s);
	for(int i = 0;i < len;i++)
	{
		int c = getnum(s[i]);
		if(!trie[p][c])//如果子节点不存在，则单词不存在 
			return 0;
		p = trie[p][c];//移动到下一个节点 
	}
	return cnt[p];//返回出现次数 
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		//初始化 
		for(int i = 0;i <=id;i++)
		{
			for(int j = 0;j <=150;j ++)
			{
				trie[i][j] = 0;
			}
		}
		for(int i = 0; i <= id;i++)
			cnt[i] = 0;
		id = 0;
		
		cin>>n>>q;	
		for(int i = 1; i<= n;i ++)
		{
			cin>>str;
			build(str);
		}
		for(int i = 1;i <= q;i ++)
		{
			cin>>str;
			printf("%d\n",find(str));
		 } 
	} 
	return 0;
}