我要成为字符串领域大神！

trie树/字典树

字典树是什么思想？我们先设定一个根节点，一般为0，每次加入新字符串时都与其相连。比如我们要插入string，看起来就是这样

然后如果我们又插入一个strange，就会变成这样

也就是说插入的时候可以直接继承志曾经出现过的前缀部分，思想就是这么个思想
具体实现就是建一个二维数组son[maxn]k，son[i][j]表示以i为父节点，他的字符为j的子节点的编号。什么叫字符为j？简单来说就是将字符种类转换为数字。比如如果只有小写英文字母，我们就会把a到z转换为0到25，如果有小写和大写字母，就转换为0到51，以此类推。
对于每个插入，遍历字符串，存在则继续遍历，不存在就新建叶子结点。对于本题则每次遍历都给路径都加1，那样对于每个查询，遍历到结尾时结尾上的值就是答案个数。
多测每次对数组清空

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
int t,idx;
int a[maxn],cnt[maxn],son[maxn][65];
char str[maxn];
int trans(char x)//transform
{
	if(x>='a'&&x<='z') return x-'a';
	if(x>='A'&&x<='Z') return x-'A'+26;
	if(x>='0'&&x<='9') return x-'0'+52;
}
void ins(char str[])//insert
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int now=trans(str[i]);
		if(!son[p][now]) son[p][now]=++idx;
		p=son[p][now];
		cnt[p]++;
		//cout<<cnt[p]<<endl;
	}
}
int query(char str[])
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int now=trans(str[i]);
		if(!son[p][now]) return 0;
		p=son[p][now];
	}
	return cnt[p];
}
int main()
{
	cin>>t;
	while(t--)
	{
		int n,q;
		scanf("%d%d",&n,&q);
		for(int i=0;i<=idx;i++)
		 for(int j=0;j<=64;j++)
		   son[i][j]=0;
		for(int i=0;i<=idx;i++)
		cnt[i]=0;
		idx=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",str);
			ins(str);
		}
		for(int i=1;i<=q;i++)
		{
			scanf("%s",str);
			printf("%d\n",query(str));
		}
	}
	return 0;
}