字典树总结

前言

初学时看来字典树还比较简单，但是有很大概率到后来会结合树形 DP。

Part 1 为什么会有字典树

在处理一些字符串问题时，经常会出现一些内存不够以及时间复杂度很高的问题，这时候我们就可以用一种树形结构来存储信息，这样及解决了内存的问题，还在某些问题中大大的节约了时间。

Part 2 字典树是怎么运行的

首先，我们考虑用一条树链来存储字符串信息，即如下图所示：

这样一条树链就表示了 Apple 这个字符串。然后我们再添加一条树链：

我们又添加了一个字符串 AppStore。但是我们发现它们有着相同的前缀，那么是不是意味着我们可以合并它们呢？这样就可以节省空间了。尝试合并后图变成了这样：

我们发现这棵树包含了刚才的两条树链，且比刚才省去了一个前缀 App。通过这种操作我们就达到了省空间的效果。尝试再加入一条树链：

这次我们发现这个单词也有相同于已处理的树内的地方，再次尝试合并：

但是这样是不可以的，破坏了字典树的树形结构，可见合并的前提是不破坏树形结构。为了保证树形结构，我们可以创造一个虚拟点

0

作为根节点，然后就可以并入这个单词了，如下图：

Part 3 字典树可以用来做什么

初学时主要有以下两点作用：

查询字典树中有没有某个字符串。
查询字典树中有几个包含某个字符串前缀的字符串。

Part 4 字典树具体怎么用代码实现

对于添加新的字符串，我们可以用一个

tot

记录全局结点编号，再用 son 数组来存储对于结点编号

u

，它的子节点

v

的编号是多少。在插入时判断当前节点有没有当前需要插入字典树的字符子节点，如果没有则添加，然后再遍历下一个子节点即可。代码如下：

CPP

void insert(string s){
	int siz = s.size(),u = 0;
	for(int i = 0;i<siz;i++){
		int v = s[i]-'a';
		if(!son[u][v])son[u][v] = ++idx;
		u = son[u][v];
		cnt[u]++;
	}
}

对于查询是否存在字符串，可以在插入时在存储字符串的树链结尾处打上标记，然后按照插入时搜索的顺序搜索，如果在途中发现没有符合要求的子节点或在终点是未发现标记即为没有此字符串，代码如下：

CPP

bool search(string s){
	int len = s.size(),cur = 0;
	for(int i = 0;i<len;i++){
		int c = s[i]-'a';
		if(son[cur][c] == 0){
            return 0;
        }
		cur = son[cur][c];
	}
	if(!vis[cur])return 0;
	return 1;	
}

然后查找给定字符串为多少个在字典树内的字符串的前缀时，不难发现如果当前字符串为另一个字符串的前缀，则表示另一个字符串的树链末端必定在表示当前字符串的树链末端的子树内，我们可以在插入时一路增加统计当前节点的子树内有多少个表示字符串的树链末端的计数器，然后查找的时候就可以直接先找到给定字符串的末端，返回记录的计数器数值即可，代码如下：

CPP

int get(string s){
	int siz = s.size(),u = 0;
	for(int i = 0;i<siz;i++){
		int v = s[i]-'a';
		if(!son[u][v]){
			return 0;
		}
		u = son[u][v];
	}	
	return cnt[u];
}

Part 5 字典树时空复杂度

查询以及插入时的复杂度取决于给定字符串的长度，即

O(len)

。空间复杂度是取决于给定的总字符数和取的字符集大小，设总字数为

S

，字符集大小为

T

个字符，那么空间复杂度就是

O(S \times T)

。

Part 6 字典树例题

P2580 于是他错误的点名开始了

这是一道比较模板的题，先插入若干个字符串，然后再查询是否存在，但是这题多了一个操作——查询是不是第一次查询。这个操作其实不难，还是用一个数组统计即可。

CPP

#include <bits/stdc++.h>
using namespace std;
int tot,trie[1000000][50],cnt[1000000];
void insert(string s){
	int len = s.size(),cur = 0;
	for(int i = 0;i<len;i++){
		int c = s[i]-'a';
		if(trie[cur][c] == 0)trie[cur][c] = ++tot;
		cur = trie[cur][c];
	}
	cnt[cur]++;
	return ;
}
void search(string s){
	int len = s.size(),cur = 0;
	for(int i = 0;i<len;i++){
		int c = s[i]-'a';
		if(trie[cur][c] == 0){
            cout<<"WRONG\n";
            return ;
        }
		cur = trie[cur][c];
	}
	if(!cnt[cur]){
		cout<<"WRONG"<<'\n';
		return ;
	}
	if(cnt[cur] == 1)cout<<"OK"<<'\n';
	else cout<<"REPEAT"<<'\n';
	cnt[cur]++;
	return ;	
}
int main(){
	int n,m;
	cin>>n;
	char x[100000];
	for(int i = 1;i<=n;i++){
		cin>>x;
		insert(x);
	}
	cin>>m;
	for(int i = 1;i<=m;i++){
		cin>>x;
		search(x);
	}
	return 0;
}

P8306 【模板】字典树

这是官方的模板，这次是查询字符串前缀，只要先插入，然后按照刚才的思路做就可以了。注意大小写敏感。

CPP

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6+20;
int son[maxn][100],idx,cnt[maxn];
void insert(string s){
	int siz = s.size(),u = 0;
	for(int i = 0;i<siz;i++){
		int v = s[i]-'0';
		if(!son[u][v])son[u][v] = ++idx;
		u = son[u][v];
		cnt[u]++;
	}
}
int get(string s){
	int siz = s.size(),u = 0;
	for(int i = 0;i<siz;i++){
		int v = s[i]-'0';
		if(!son[u][v]){
			return 0;
		}
		u = son[u][v];
	}	
	return cnt[u];
}
int main(){
	int t;
	cin>>t;
	int n,m;
	string x;
	while(t--){
		for(int i=0;i<=idx;i++){
			memset(son[i],0,sizeof(son[i]));
			cnt[i]=0;
		}
		idx = 0;
		cin>>n>>m;		
		for(int i = 1;i<=n;i++)cin>>x,insert(x);
		for(int i = 1;i<=m;i++){
			cin>>x;
			cout<<get(x)<<'\n';
		}
	}
	return 0;
}

完结撒花~~

文章操作

前言