什么是字典树
先看一张图：
这是一棵由 "abc","ac","da"组成的字典树
容易发现，字典树的边就是字符串中的字母，每个字符串都被表示为从根节点到叶子节点的路径上所有字符所组成的字符串。
同时我们可以看到，第 \(i\) 个字符的儿子时第 \(i+1\) 个字符
当对若干个字符串进行插入（建树）操作时，两两字符串的公共部分就会沿着树走下来，在不同处分叉
字典树的操作
插入一个字符串：
例如，我们在上面的树中插入一个字符串 "dbc"
我们从根节点向下遍历，先插入字符 'd' ，由于已经有了一条为 'd' 的边，所以我们直接从第 \(5\) 个点进行下一次插入
接下来插入 'b' ,因为当前节点没有一条为 'b' 的边，所以我们创建一个新节点，连一条边权为 'b' 的新边
最后插入字符 'c' ，因为当前节点没有一条为 'c' 的边，所以我们创建一个新节点，连一条边权为 'c' 的新边
到此就完成了插入操作
插入后的树是这样的
这一步思想很简单，代码也是很简单的
inline void insert(string s) {
int u=0,len=s.length();
for(int i=0;i<len;++i) {
int c=idx(s[i]);
if(!ch[u][c]) {
memset(ch[siz],0,sizeof(ch[siz]));
ch[u][c]=siz++; // 创建新节点
}
u=ch[u][c]; // 继续遍历
}
}
查找一个字符串是否为一个字符串的前缀：
还是看刚刚的那棵树
我们从树根往下遍历就，如果当前节点有一条为这个字符的边，那就继续查找，否则即为没有出现过
代码写起来也是和插入很像的
inline bool find(string s) {
int u=0,len=s.length();
for(int i=0;i<len;++i) {
int c=idx(s[i]);
if(!ch[u][c])
return false;
u=ch[u][c];
}
return true;
}
习题：
简单的字典树模板，不过值判断是否相等而不是前缀，在插入时记录一下每个字符串的结尾，查询时判断一下是不是在结尾
对于 "REPEAT" ，我们用一个数组在查询时记录一下这个字符串有没有被查找过就行了
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=5e5+7;
struct Trie {
int ch[N][26],siz;
bool val[N];
bool p[N];
inline Trie() {
siz=1;
memset(ch,0,sizeof(ch));
memset(val,false,sizeof(val));
memset(p,false,sizeof(p));
}
inline int idx(char c) {
return c-'a';
}
inline void insert(string s) {
int u=0,len=s.length();
for(int i=0;i<len;++i) {
int c=idx(s[i]);
if(!ch[u][c])
ch[u][c]=siz++;
u=ch[u][c];
}
p[u]=true;
}
inline bool find(string s) {
int u=0,len=s.length();
for(int i=0;i<len;++i) {
int c=idx(s[i]);
if(!ch[u][c])
return puts("WRONG"),false;
u=ch[u][c];
}
if(!p[u])
return puts("WRONG"),false;
if(!val[u]) {
val[u]=true;
puts("OK");
}
else
puts("REPEAT");
return true;
}
}trie;
string str;
int n,m;
signed main() {
scanf("%d",&n);
for(;n;--n) {
cin>>str;
trie.insert(str);
}
scanf("%d",&m);
for(;m;--m) {
cin>>str;
trie.find(str);
}
return 0;
}
字典树模板题，在插入之前判断一下是不是之前某个字符串的前缀
但是这样是错误的！
注意到一个性质，若 \(a\) 串是 \(b\) 串的前缀，则 \(a\) 串的长度不可能大于 \(b\) 串
所以我们每次插入时，有可能先插入了 \(a\) ，后面的 \(b\) 就不会被判断为有子串了
排序一下就可以解决
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e4+7;
struct Trie {
int ch[N][11],siz;
inline Trie() {
clear();
}
inline void clear() {
siz=1;
memset(ch[0],0,sizeof(ch[0]));
}
inline int idx(char c) {
return c&15;
}
inline void insert(string s) {
int u=0,len=s.length();
for(int i=0;i<len;++i) {
int c=idx(s[i]);
if(!ch[u][c]) {
memset(ch[siz],0,sizeof(ch[siz]));
ch[u][c]=siz++;
}
u=ch[u][c];
}
}
inline bool find(string s) {
int u=0,len=s.length();
for(int i=0;i<len;++i) {
int c=idx(s[i]);
if(!ch[u][c])
return false;
u=ch[u][c];
}
return true;
}
}trie;
string s[N];
int T,n;
signed main() {
scanf("%d",&T);
for(;T;--T) {
scanf("%d",&n);
trie.clear();
bool ans=false;
for(int i=1;i<=n;++i)
cin>>s[i];
sort(s+1,s+1+n);
for(int i=n;i;--i) { // 因为是从小到大排,所以要从后面开始遍历
ans|=trie.find(s[i]);
trie.insert(s[i]);
}
puts(ans ? "NO" : "YES");
}
return 0;
}
01 Trie 树
Trie树就只能对着字符串乱搞？
我们来看这道例题：P4551 最长异或路径
首先，我们知道异或有一个性质 \(a \oplus b \oplus b \oplus c = a \oplus c\)
那么树上任意两点 \(u \to v\) 路径的异或和就等于 \(u \to \tt{根节点} \oplus \tt{根节点} \to v\)
我们可以 dfs 一遍求出所有点到根节点的路径异或的值 \(val_i\)
问题就转化为了在 \(val\) 数组中 \(val_i \oplus val_j\) 的最大值
这时候我们就可以用01 Trie 树！
考虑将所有的数的二进制插入一个 Trie 树中，接下来就可以用贪心的策略，在遍历某一位时，优先选择后与他相反的那一步，如果那一步为空，则走与这一位相同的那一步
这样我们只要枚举每一个数字，并对这个数在字典树中进行查询，取个最大值就行了
太抽象？
我们看插入 \(3,5,7\) 这 \(3\) 个数后的字典树：
我们来看寻找与 \(3\) 异或值最大的数
先将 \(3\) 拆成 \(4\) 为二进制数 \(0011\)
先看第一个数字 \(0\) ，因为当前节点没有边为 \(1\) 的儿子，所以只能走到节点 \(1\)
再看第二个数字 \(0\) ，因为 \(1\) 这个节点有一个边为 \(1\) 的儿子，根据贪心策略，我们走到第 \(5\) 个节点
第三个数字是 \(1\) ，因为 \(5\) 这个节点有一个边为 \(0\) 的儿子，所以走到第 \(6\) 个节点
最后一个数字是 \(1\) ，因为为 \(6\) 这个节点没有边为 \(1\) 的儿子，所以只能走到节点 \(1\)
所以我们最后找到的数是 \(5\) ，事实证明，这是对的（ $ 3 \oplus 5 > 3 \oplus 7 $ ）
到此就完成了本题
A了这道题，祝你们成功
代码：
#include <cstdio>
#include <vector>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=1e6+7;
struct Trie {
int ch[N][2];
int siz;
inline Trie() {
siz=0;
memset(ch,0,sizeof(ch));
}
inline void insert(int x) {
int u=0;
for(int i=31;~i;--i) {
int c=x>>i&1;
if(!ch[u][c])
ch[u][c]=++siz;
u=ch[u][c];
}
}
inline int query(int x) {
int u=0,res=0;
for(int i=31;~i;--i) {
int c=x>>i&1;
if(ch[u][!c]) {
u=ch[u][!c];
res=(res<<1)+(!c);
}
else {
u=ch[u][c];
res=(res<<1)+c;
}
}
return res;
}
}trie;
vector<pair<int,int> > edge[N];
int val[N];
int n,ans;
inline void dfs(int u,int sum) {
val[u]=sum;
for(int i=0,v,w;i<edge[u].size();++i) {
v=edge[u][i].first,w=edge[u][i].second;
dfs(v,sum^w);
}
}
signed main() {
scanf("%d",&n);
for(int i=1,u,v,w;i<n;++i) {
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back({v,w});
}
dfs(1,0);
for(int i=1;i<=n;++i) {
trie.insert(val[i]);
ans=max(ans,val[i]^trie.query(val[i]));
}
printf("%d",ans);
return 0;
}