Trie树：是一种能够高效存储和查找字符串集合的数据结构
Trie字符串统计
思路：
（笔记来自AcWing 835. Trie字符串统计 - AcWing）
代码如下：
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int son[N][26]; //trie树每个点的所有儿子(最多26个) //[N]父节点 []子节点
int cnt[N];//以当前点结尾的单词有多少个
int idx;//存的是当前已经用到了哪个下标(未用)
//idx=0 既是根节点 又是空结点(一个点没有子节点 会让它指向0)
//1.insert函数: trie的插入:
void insert(string str)
{
int p = 0; //根节点为0
for (int i = 0; i < str.size(); i ++) //char字符串以'\0'结尾
{
int u = str[i] - 'a'; //将字符串的小写字母转换为0~25
if (!son[p][u]) //如果p下面没有路径(没有子节点'u')找到u 则创建对应路径
son[p][u] = ++ idx ;
p = son[p][u]; //下次下移到这个结点开始寻找
}
cnt[p] ++; //以p节点结尾的 字符串有多少
}
//query函数: 查询指定字符串出现次数
int query(string str)
{
int p = 0;
for (int i = 0; i < str.size(); i ++)
{
int u = str[i] - 'a';
if (!son[p][u]) //如果没有
return 0;
p = son[p][u];//下次下移到这个结点开始寻找
}
//指定字符串 循环结束
return cnt[p]; //返回这个字符串的数量
}
int main()
{
int n;
cin >> n;
while (n --)
{
char ch;
string s;
cin >> ch >> s;
if (ch == 'I')
insert(s);
else
cout << query(s) << endl;
}
return 0;
}
最大异或对
活动 - AcWing
思路：
1.用Trie树存储每个数的二进制数形式
2.遍历这课树，每一位寻找与当前位u不同的数
3.若找到则向高位移动再加1（res*2 + 1），若找不到则向高位移动加0（res*2 + 0）
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int const N=100010,M=31*N;
int n;
int a[N];
int son[M][2],idx;
//M代表一个数字串二进制可以到多长
void insert(int x)
{
int p=0; //根节点
for(int i=30;i>=0;i--)
{
int u=x>>i&1; /取X的第i位的二进制数是什么 x>>k&1(前面的模板)
if(!son[p][u]) son[p][u]=++idx; ///如果插入中发现没有该子节点,开出这条路
p=son[p][u]; //指针指向下一层
}
}
int search(int x)
{
int p=0;int res=0;
for(int i=30;i>=0;i--)
{ ///从最大位开始找
int u=x>>i&1;
if(son[p][!u]) 如果当前层有对应的不相同的数
{ ///p指针就指到不同数的地址
p=son[p][!u];
res=res*2+1;
///*2相当左移一位 然后如果找到对应位上不同的数res+1 例如 001
} /// 010
else --->011 //刚开始找0的时候是一样的所以+0 到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
{
p=son[p][u];
res=res*2+0;
}
}
return res;
}
int main(void)
{
cin.tie(0);
cin>>n;
idx=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]);
}
int res=0;
for(int i=0;i<n;i++)
{
res=max(res,search(a[i])); ///search(a[i])查找的是a[i]值的最大与或值
}
cout<<res<<endl;
}
