Trie树 (字典树)

什么是trie树

trie树是一种用来查找字符串的树形结构, 利用字符串公共信息把多个字符串存储成一棵树, 节约内存, 加快检索速度
这是一棵字典树

trie树的性质

1.根节点为空, 其余每个节点只对应一个字符
2.从根节点到某一节点, 路径中经过的字符连接起来会形成一个字符串
3.要求: 每个节点的所有子节点包含的字符都 互不相同

trie树的特点

前缀相同的子串共享相同的祖先节点
查询复杂度为O(length)

算法思想

遇到能用的相同前缀就直接用, 不能用就新建

注意: 要提前用二维数组建好所有后继 (如小写字母组成的字典树就要建26个后继)

代码实现

1.字符种数决定了每个点的出度, 也就是trie数组的第二维 (空间换时间)
2.trie数组下标表示字符的相对位置
3.采用末尾标记确定是否是字符串

插入

code

inline void insert(char *s){
	int r=1,len=strlen(s);
	for(int i=0;i<len;i++){
		int c=s[i]-'a';
		if(!trie[r][c]) trie[r][c]=++cnt;  //查询当前字符是否为树上某一节点, 如果不是就新建
		r=trie[r][c];  //根节点设置为当前节点, 顺着trie树往下找
	}
	v[r]++;  //末尾标记
}

查询

code

inline int query(char *s){
	int r=1,len=strlen(s);
	for(int i=0;i<len;i++){
		int c=s[i]-'a';
		r=trie[r][c];
		if(!r) return 0; //没有找到当前字符--匹配的字符串不存在, 直接返回
	}
	return v[r];  //末尾标记次数为出现次数
}

例题

UVA11362 Phone List

题目链接

题意: 在多个字符串中查询一个串是否是另一个串的前缀
分为2种情况:
1.当前串为之前的串的前缀
2.当前串为后来的串的前缀
只需在插入时对标记数组稍作判断
详情见代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int trie[N][10],cnt,pre[N];
inline bool insert(char *s){
	int r=1,len=strlen(s);
	bool f=false;
	for(int i=0;i<len;i++){
		int c=s[i]-'0';
		if(!trie[r][c]) trie[r][c]=++cnt;
		else if(i==len-1) f=true; //已经检索到当前串最后一个--当前串为之前的串的前缀
		r=trie[r][c];
		if(pre[r]) f=true; //之前的串为当前串的前缀
	}
	pre[r]=1; //末尾标记
	return f;
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		memset(pre,0,sizeof(pre));
		memset(trie,0,sizeof(trie));
		bool f=false;
		char s[20]; cnt=1;
		int n; scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			if(insert(s)) f=true; 
		}
		f?puts("NO"):puts("YES");
	}
	return 0;
}

The XOR Largest Pair

此处是题目

接下来引进 01trie

01trie 顾名思义每个节点最多只有2个子节点, 我们用01trie存下每个数对应的每位二进制数字, 查找时反着找, 找到一位答案就变成 \(ans\times 2+1\), 否则是\(ans\times 2\) (为了优化速度可使用位运算)

上代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],trie[N*32][2],res,cnt=1;
inline void insert(int x){
	int r=1;
	for(int i=31;i>=0;i--){
		int c=(x>>i)&1;
		if(!trie[r][c]) trie[r][c]=++cnt;
		r=trie[r][c];
	}
}
inline int query(int x){
	int r=1,res=0;
	for(int i=31;i>=0;i--){
		int c=(x>>i)&1;
		if(trie[r][!c]) //找与当前位相反的节点
			r=trie[r][!c],res=res<<1|1;
		else r=trie[r][c],res=res<<1;
	}
	return res;
}
int main(){
	int n; scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		insert(a[i]);
	}
	for(int i=1;i<=n;i++)
		res=max(res,query(a[i]));
	cout<<res;
	return 0;
}

END

☆⌒(*＾-゜)v thx!!