字典树

Trie 树，即字典树，是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。

Trie 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

性质

1. 字典树的根节点不代表任一个字符，其余所有节点都包含一个字符。

2. 从字典树的根部开始走，路径上所有的字符 串起来就是当前节点所代表的字符串。

3. 每一个节点的子节点所代表的字符各不相同。

就像这张图

字典树的操作

练习

模板题

本题的大意是给你一堆字符串，然后在问你里面有多少个串去掉后面数个字符后能与给你的字符串相同。
本题最简单的做法就是建一棵字典树，然后按找顺序查询给你的字符串，到了最后一个之后，当前点的子树大小就是答案。
代码实现

#include<bits/stdc++.h>
#define N 3000010
using namespace std;
int T,q,n,t[N][65],cnt[N],idx;
string s;
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 add(string s1)
{
	int p=0,len=s1.size();
	for(int i=0;i<len;i++)
	{
		int c=getnum(s1[i]);
		if(!t[p][c])
			t[p][c]=++idx;
		p=t[p][c];
		cnt[p]++;
	}
}
int fid(string s1)
{
	int p=0,len=s1.size();
	for(int i=0;i<len;i++)
	{
		int c=getnum(s1[i]);
		if(!t[p][c])
			return 0;
		p=t[p][c];
	}
	return cnt[p];
}
void qk()
{
	for(int i=0;i<=idx;i++)
		for(int j=0;j<=122;j++)
			t[i][j]=0;
	for(int i=0;i<=idx;i++)
		cnt[i]=0;
	idx=0;
}
int main()
{
	cin>>T;
	while(T--)
	{
		qk();
		cin>>n>>q;
		for(int i=1;i<=n;i++)
		{
			cin>>s;
			add(s);
		}
		for(int i=1;i<=q;i++)
		{
			cin>>s;
			cout<<fid(s)<<endl;
		}
	}
	return 0;
}