浅谈字典树

原创

Clare613

修改于 2025-07-15 11:07:47

1670

文章被收录于专栏：字典树字典树

前言：

本期我们讲一下字典树。话不多说，步入正题。

何为字典树：

顾名思义，这是一个类似于字典的树。我们想一下，要有一个字典得先把词语加进去。假设有一个字典树，里面分别有单词 apple,banana,application,bad 这四个单词，那么这个字典树就长这样：\

我们可以发现，这些单词的首字母最开始都是连接着 0，相当于超级起点。我们又可以发现，单词其实是有一部分重复的，也就是说相同部分可以重复利用。

有什么用：

不难发现，字典树有着先天的优势来处理各种各样的前缀问题，那么它的作用也就是存在性和前缀问题。\

接着我们进行深度思考，其实可以发现，字典树还可以做异或的问题。因为前缀往往更大，后缀加起来也比不上，这样只需对每一步看一下 0/1 即可。

例题：

这里挑选了几道重要的题目讲，没讲的视为练习。

P8306 【模板】字典树：

基本题，用于存模板，模板如下：

#include<bits/stdc++.h>
using namespace std;
int trie[3000005][100];
int ToT;
int cnt[3000005];
void mn(string x){
	int u=0;
	for(int i=0;i<x.size();i++){
		if(trie[u][x[i]-'0']==0){
			trie[u][x[i]-'0']=++ToT; 
		}
		u=trie[u][x[i]-'0'];
		cnt[u]++;
	}
}
int se(string x){
	int u=0;
	for(int i=0;i<x.size();i++){
		u=trie[u][x[i]-'0'];
		if(cnt[u]==0) break;
	}
	return cnt[u];
}
string x[100005];
signed main(){
	int T;
	cin>>T;
	while(T--){
		ToT=0;
		int n,q,sum=0;
		cin>>n>>q;
		for(int i=1;i<=n;i++){
			cin>>x[i];
			sum+=int(x[i].size());
		}
		for(int i=0;i<=sum;i++){
			cnt[i]=0;
			for(int j=0;j<100;j++){
				trie[i][j]=0;
			}
		}
		for(int i=1;i<=n;i++){
			mn(x[i]);
		}
		for(int i=1;i<=q;i++){
			cin>>x[i];
			cout<<se(x[i])<<"\n";
		}
	}
	return 0;
}

对应练习：P2580 于是他错误的点名开始了

P10471 最大异或对 The XOR Largest Pair：

这就是异或题。解法就是建了树后一位一位地找，最后取最大值。具体的我已讲过。

#include<bits/stdc++.h>
using namespace std;
int ToT,trie[3200005][2];
int cnt[3200005];
void mn(int x){
	int u=0;
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		if(trie[u][c]==0){
			trie[u][c]=++ToT;
		}
		u=trie[u][c];
	}
}
int ans=0;
int se(int x){
	int u=0,ans=0;;
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		if(trie[u][c^1]!=0){
			u=trie[u][c^1];
			ans+=(1<<i);
		}
		else u=trie[u][c];
	}
	return ans;
}
int x[100005];
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
    int ans=0;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		mn(x[i]);
		ans=max(ans,se(x[i]));
	}
	cout<<ans;
	return 0;
}

对应练习：P4551 最长异或路径。

P2922 USACO08DEC Secret Message G：

这道题就是明显的前缀问题，我们需要对于两种情况分别加和即可。

#include<bits/stdc++.h>
using namespace std;
int trie[500005][2];
int cnt1[500005];
int cnt2[500005];
int ToT;
void mn(string x){
	int u=0;
	for(int i=0;i<x.size();i++){
		if(trie[u][x[i]-'0']==0){
			trie[u][x[i]-'0']=++ToT;
		}
		u=trie[u][x[i]-'0'];
		cnt2[u]++;
	}
	cnt1[u]++;
}
int se(string x){
	int u=0,ans=0;
	for(int i=0;i<x.size();i++){
		if(trie[u][x[i]-'0']==0){
			trie[u][x[i]-'0']=++ToT;
		}
		if(!trie[u][x[i]-'0']) return ans;
		u=trie[u][x[i]-'0'];
		ans+=cnt1[u];
	}
	if(u){
		ans+=cnt2[u]-cnt1[u];
	}
	return ans;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string x="";
		int w;
		cin>>w;
		for(int j=1;j<=w;j++){
			char y;
			cin>>y;
			x=x+y;
		}
		mn(x);
	}
	for(int i=1;i<=m;i++){
		string x="";
		int w;
		cin>>w;
		for(int j=1;j<=w;j++){
			char y;
			cin>>y;
			x=x+y;
		}
		cout<<se(x)<<"\n";
	}
	return 0;
}