字典树的介绍
字典树也叫(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;
}
标签:cnt,idx,Trie,++,son,int,define,字典
From: https://www.cnblogs.com/TLSnail/p/18364586