字典树的介绍
字典树也叫（Trie树），字典树有插入和查询两个操作，我们先假设我们已经插入了单词 be、fake、beef、face 这几个单词，那么我们可以建树。
当我们查询 be、fa、fAKe、fac 时，答案分别为：\(2,2,0,1\)。
字典树的插入
我们可以给树上的每个节点标号，比如上面的树，可标为：
根节点永远都是 \(0\)，而其他节点，按访问顺序来标号。
我们定义 son[i][w] 表示现在的编号 i 的下一个字符是 w 的编号是多少，比如，编号 i 所对应的字符串是 t[i] 那么 t[son[i][w]]=t[i]+w。
设一个变量 p，表示现在访问到的节点编号是多少，一开始的时候 p=0，然后如果 son[p][w]=0 那么就新建一个节点编号，即 son[p][w]=++idx。接着 \(p\) 赋值成下一个节点的编号即 son[p][w]，然后对应字符串出现次数 cnt[p] 加一。
代码：
int idx=0;
void insert(char *s){
int p=0;
for(int i=0,w;w=s[i];i++){
if(!son[p][w])son[p][w]=++idx;
p=son[p][w];
cnt[p]++;
}
}
字典树的查询
首先还是设一个变量 p 表示现在访问到的节点编号是多少，p 一开始在根节点，然后如果 son[p][w]=0 那么就表示没有这种字符串，即返回 \(0\)，否则的话，我们继续访问，最后我们枚举完整个字符串，即查询到 s 字符串对应的编号 p，返回 cnt[p] 即可。
int query(char *s){
int p=0;
for(int i=0,w;w=s[i];i++){
if(!son[p][w])return 0;
p=son[p][w];
}
return cnt[p];
}
模板代码
就是普通的模板，卡常卡过就行了。
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;i++)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;i--)
#define endl '\n'
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define vi vector<int>
using ll=long long;
using ull=unsigned long long;
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=3e6+10,MAXM=1e5+10;
int T,n,q,cnt[MAXN],idx;
char s[MAXM];
map<char,int>son[MAXN];
void insert(char *s){
int p=0;
for(int i=0,w;w=s[i];i++){
if(!son[p][w]){
son[p][w]=++idx;
cnt[idx]=0;
}
p=son[p][w];
cnt[p]++;
}
}
int query(char *s){
int p=0;
for(int i=0,w;w=s[i];i++){
if(!son[p][w])return 0;
p=son[p][w];
}
return cnt[p];
}
void solve(){
rep(0,idx,i)son[i].clear();
idx=0;
scanf("%d%d",&n,&q);
rep(1,n,i){
scanf("%s",s);
insert(s);
}
while(q--){
scanf("%s",s);
printf("%d\n",query(s));
}
}
int main(){
cin>>T;
while(T--)
solve();
return 0;
}