Trie树
Trie树又叫前缀树，字典树。
作用高效的存储和查找字符串集合的数据结构
Trie储存字符串
对于树的存储，本题本质上是使用的二维数组来存储树，行代表当前第几个几点，列代表当前节点的几个儿子。
#include <iostream>
using namespace std;
const int N = 10e5+10;
int n;
char str[N]; // 用来存放一整个字符串 可能N个字符作为一个整体输入到str
int son[N][26]; // 用来存放这个Trie树
int cnt[N]; // 用来存放每个字符串出现了多少次
int idx;
void insert(char* str){ // 将一个字符串插入到Trie树中
int p = 0; // 父节点 0则意味着初始父节点
for(int i = 0; str[i] != 0;i++){ // 遍历每个输入的字符串str
int u = str[i] - 'a'; // 将每个字符映射到数字上 这样才能在son数组中使用u索引
if(son[p][u] == 0){ // 如果遍历到这个字符串的最后一个字符0 使用一个新的idx创建一个节点
son[p][u] = ++idx;
}
p = son[p][u]; // 更新新的p节点
//cout << p << " ";
}
cnt[p] ++ ; // 遍历完每个节点的时候，记得标记加一 共查询使用
}
int query(char* str){ // 查询这个字符串中有几个当前字符串 每个字符串的个数其实都在一个数组中排好
int p = 0;
for(int i = 0; str[i] != 0;i++){
int u = str[i] - 'a';
if(son[p][u] == 0){ // 字符串访问快结束的时候
return 0;
}
p = son[p][u];
//cout << p << " ";
}
return cnt[p];
}
int main(){
cin >> n;
char op[2]; // 这里开两个是因为以后要以%s输入的字符串，末尾会有一个\0
while(n--){
scanf("%s%s",&op,&str);
if(op[0] == 'I'){
//printf("------------");
insert(str);
}else if(op[0] == 'Q'){
//printf("------------");
printf("%d\n",query(str));
// puts("");
}
}
return 0;
}
Trie树的应用：最大异或对
// 暴力做法 只能过5/9，因此需要使用Trie树 O(n^{2}) n方是十的十次方所以就会超时
int res = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<i;j++){
res = max(res,q[i]^q[j]);
}
}
#include <iostream>
// 时间复杂度O(31*n)~O(nlogn)
// c++一秒内可以算大概100万-1000万次 10^7-10^8 所以必须使用算法，不能暴力，暴力就会超时
using namespace std;
const int N = 10e5+10;
int a[N];
int son[N*31][2]; // 第一维度是N个数总共的二进制位，第二维是每个二进制的选择0or1
int n;
int idx;
void insert(int x){ // 自己手动构建一个二叉树
int p = 0;
for(int i = 30; i>=0; i--){
int t = (x >> i & 1); // 把x的二进制表示的第i位抠出来 非0即1
if(!son[p][t]) son[p][t] = ++idx; // idx没有实际含义 记录的只是一些用过的节点序号12345678
p = son[p][t];
}
// cout << p << endl;
}
int find(int x){ // 从上面构建的二叉树中找到自己需要的值 返回与x异或后 最大的数
int p = 0,res = 0;
for(int i = 30;i>=0;i--){
int t = (x >> i & 1);
if(son[p][!t]){
p = son[p][!t];
res = res *2 + 1;
}else{
p = son[p][t];
res = res * 2 + 0;
}
}
return res;
}
int main(){
cin >> n;
int res;
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i = 0;i<n;i++){
insert(a[i]);
}
for(int i = 0;i<n;i++){
res = max(res,find(a[i]));
}
cout << res;
return 0;
}
