Trie树（字典树）/（前缀树）
字典树的概念
注意:
（1）在一条边上存字符
（2）如果前缀相同的话，就可以实现复用。
（3）从根节点出发到某个节点的路径就代表一个字符串
（4）
有->复用
没有->创建（5）
维护信息：
pass:标记当前节点一共经过多少次
end:b=标记当前节点是以多少个字符串作为结尾
字典树的实现
准备工作
tree[N][26] :里面记录的是 当前的N节点 可以通过字母到达的结点
如
0号结点可以通过a到达1号结点
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6+10;//N表述字符串里面有多少个字符
int tree[N][26];//N表示如上，26表示有26个字母
int p[N];//表示每个结点的出现次数
int e[N];//表示各个字符串的出现次数，记录在叶子结点
int idx;//表示给新来的结点创建插入操作
//插入操作
void insert(string& s)
{
int cur = 0;//表示从根节点出发
p[cur]++;//根节点经过次数+1
for(auto ch:s)//遍历字符串
{
int path = ch - 'a';//当前字符的当前节点的下标
if(tree[cur][path] == 0)tree[cur][path] = ++idx;//没有，那就创建一个
//继续维护,cur 可以根据 ch 来到下标tree[cur][path]
cur = tree[cur][path];
p[cur]++;//++
}
e[cur]++;//最后的叶子结点++,表示该字符串出现次数+1
}
查询操作
查询前缀
1.P8306 【模板】字典树 - 洛谷
#include<iostream>
#include<cstring>
using namespace std;
const int N = 3e6 + 10;
int tree[N][62];
int p[N];
int idx = 0;
int get_num(char ch)
{
if (ch >= 'a' && ch <= 'z')return ch - 'a';
else if (ch >= 'A' && ch <= 'Z')return ch - 'A' + 26;
else if (ch >= '0' && ch <= '9')return ch - '0' + 52;
}
void insert(string& s)
{
int cur = 0;
p[cur]++;
for (auto ch : s)
{
int path = get_num(ch);
if (tree[cur][path] == 0)tree[cur][path] = ++idx;
cur = tree[cur][path];
p[cur]++;
}
}
int find_pre(string& s)
{
int cur = 0;
for (auto ch : s)
{
int path = get_num(ch);
if (tree[cur][path] == 0)return 0;
cur = tree[cur][path];
}
return p[cur];
}
int T, n, q;
int main()
{
cin >> T;
while (T--)
{
/*memset(tree, 0, sizeof(tree));
memset(p, 0, sizeof(p));*///用这个进行清空开销太大
for (int i = 0; i < idx; i++)
{
for (int j = 0; j < 62; j++)
{
tree[i][j] = 0;
}
}
for (int i = 0; i < idx; i++)p[i] = 0;
idx = 0;
cin >> n>>q;
while (n--)
{
string s; cin >> s;
insert(s);
}
while (q--)
{
string pre; cin >> pre;
cout << find_pre(pre) << endl;
}
}
}2.P2580 于是他错误的点名开始了 - 洛谷
#include<iostream>
using namespace std;
const int N = 5e5 + 10;
//N表示总字符的个数
//== 字符串的个数 * 最大字符串的长度
int e[N];
int tree[N][26];
int idx;
void insert(string& s)
{
int cur = 0;
for (auto ch : s)
{
int path = ch - 'a';
if (tree[cur][path] == 0)tree[cur][path] = ++idx;
cur = tree[cur][path];
}
e[cur]++;
}
int find_name(string& s)
{
int cur = 0;
for (auto ch : s)
{
int path = ch - 'a';
if (tree[cur][path] == 0)return 0;
cur = tree[cur][path];
}
if (e[cur] > 0)
{
e[cur] = -1;
return 1;
}
return e[cur];
}
int n, m;
int main()
{
cin >> n;
while (n--)
{
string s; cin >> s;
insert(s);
}
cin >> m;
while (m--)
{
string s; cin >> s;
if (find_name(s) == 1)cout << "OK" << endl;
else if (find_name(s) == -1)cout << "REPEAT" << endl;
else cout << "WRONG" << endl;
}
}#include<iostream> using namespace std; const int N = 5e5 + 10; //N表示总字符的个数 //== 字符串的个数 * 最大字符串的长度 int e[N]; int tree[N][26]; int idx;N:表示总字符的个数，总的字符串中一共有多少个字符
3.P10471 最大异或对 The XOR Largest Pair - 洛谷
贪心，除了最高位是0，其他的全是1那么就是最大的
（1） 利用字典树：先把数字按照0 1 的二进制顺序插如tree中
（2）当来查找时，对于每一个x找除了最高位外，其余二进制位都相反的数字，此时两者异或最大，-->是否存在，
如果存在的话，那就ret = 0 ,ret |= (1<<1);和对应的二进制位进行异或，记录数据
如果不存在，那就贪不了，只可以按照原来的继续遍历下去
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int tree[32 * N][2];
int idx;
void insert(int x)
{
int cur = 0;
for (int i = 31; i >= 0; i--)//按照二进制位从前向后的顺序插入字典树种
{
int path = ((x >> i) & 1);
if (tree[cur][path] == 0)tree[cur][path] = ++idx;
cur = tree[cur][path];
}
}
int find(int x)
{
int ret = 0;
int cur = 0;
for (int i = 31; i >= 0; i--)
{
int path = ((x >> i) & 1);
//当来查找时，对于每一个x找除了最高位外，其余二进制位都相反的数字，此时两者异或最大，-- > 是否存在
if (tree[cur][path ^ 1])//如果存在的话，那就ret = 0 ,ret |= (1<<1);和对应的二进制位进行异或，记录数据
{
ret |= (1 << i);
cur = tree[cur][path ^ 1];
}
else//如果不存在，那就贪不了，只可以按照原来的继续遍历下去
{
cur = tree[cur][path];
}
}
return ret;
}
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
insert(a[i]);
}
int ret = 0;
for (int i = 1; i <= n; i++)
{
ret = max(ret, find(a[i]));//找每个的最大异或结果
}
cout << ret << endl;
return 0;
}