Trie树
字典树，又称前缀树，是用于快速处理字符串的问题，能做到快速查找到一些字符串上的信息。
另外，Trie树在实现高效的同时，会损耗更多的空间，所以Trie是一种以空间换时间的算法。
Trie树的思想
我也不明白怎么表达，我们看图吧！
Kur1su the great god
理解了吗？没理解我再想想办法。
我们用字典树干嘛？是不是更快的查询？那么在上面的trie树上是如何体现的呢？比如说我要查"great"，那么我的查询过程就是 。从树上可以知道"great"和"god"的公共前缀是'g'。
从树上可以看出，想要插入一个字符串，就顺藤摸瓜一波，如果摸到一半，藤断了，那么我们就另起门户，按照字符串中的顺序新建一些节点连接在之前藤的末尾就好。如果你插入完了整个字符串，结果藤还没断，那么我们就给这个节点打个标记，表明这里是某个字符串的结尾。
这样的话，对于每次插入复杂度就是o(len(s))。
上面是插入的过程，那么你再想想查询呢？是不是一个道理！也是一直向下摸，不同点在于，如果你的藤没断，但是这个位置的没有打标记，这样，即使你在这个树上找到了字符串，但也是没找到的，只能说有一个字符串的前缀是它。对于每次查询复杂度就是o(len(s))。
Trie的实现
看了这么久，你也应该能想到node要怎么写了吧。
节点
struct node
{
int son[26];//我们这里只考虑小写字母,要是想要把全部字符都放进去，你这开大点就好。
bool f;//这个就是我们终点标记。
} trie[maxn];插入操作
void insert(string s)
{
int now=0;//根节点为0
int len=s.length();//需要插入的串的长度
for(int i=0;i<len;i++)
{
if( trie[now].son[s[i]-'a'] )//如果在之前插入过了部分前缀一样的字符串，就不用创建新的点了，也就是顺藤摸瓜的过程
{
now=trie[now].son[s[i]-'a'];
}
else//藤断了，就要自己创建新的节点。
{
trie[now].son[s[i]-'a']=num++;
now=trie[now].son[s[i]-'a'];
}
}
trie[now].f=1;//终点标记的修改
}查询操作
void find(string s)//返回值类型视具体情况
{
int now=0;
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if( trie[now].son[s[i]-'a'] )
{
now=trie[now].son[ s[i]-'a'];
}
else
{
cout<<"查询失败"<<endl;
return ;
}
}
if( trie[now].f)
{
cout<<"查询成功"<<endl;
return ;
}
else
{
cout<<"查询失败"<<endl;
return ;
}
}这么一来字典树的基本操作你就学会了！
来用我练习的题来检测自己吧！
练习题
练习题解答
P2580 于是他错误的点名开始了
思路：就是查询每个串是否存在，若存在再看是不是第一次被查询。
//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=3e6+7;//这个值大概是node的son数组大小与题目规模的乘积，往大了开就好。
const double pi=acos(-1);
using namespace std;
int t,n,m;
int num=1;//这里也可以写成0，下面insert 的时候改成++num就好
struct node
{
int son[26];//全是小写字母的字符串，数组大小开26，27也可以
bool f;//表示这里是不是某个字符串的最后一个字符
int cnt;//这是为了本题而增加的一个标志，表示这个字符串是否有被查询过。
} trie [maxn];
void insert(string s)
{
int len = s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'a'])
{
now=trie[now].son[s[i]-'a'];
}
else
{
trie[now].son[s[i]-'a']=num++;
now=trie[now].son[s[i]-'a'];
}
}
//别忘记打上终点标记
trie[now].f = 1;
return ;
}
void find(string s)
{
int len = s.length();
int now = 0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'a'])
{
now=trie[now].son[s[i]-'a'];
}
else
{
cout<<"WRONG"<<endl;
return ;
}
}
if(! trie[now].f )
{
cout<<"WRONG"<<endl;
return ;
}
else
{
if(! trie[now].cnt)
{
cout<<"OK"<<endl;
trie[now].cnt++;
return ;
}
else
{
cout<<"REPEAT"<<endl;
return ;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
insert(s);
}
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s;
find(s);
}
return 0;
}
phone list
思路：跟上面一样，可以先把所有的串放进VECTOR，然后执行插入操作，最后再对每个串进行查询操作，查询到前缀串，就输出NO，否则YES。
//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e6+7;
const double pi=acos(-1);
using namespace std;
struct node
{
int son [10];
int f;
} trie[maxn];
int num=0;//这次用的是0，所以下面是++num
void insert(string s)
{
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'] !=0 )
{
now=trie[now].son[s[i]-'0'];
}
else
{
trie[now].son[s[i]-'0']=++num;
now=trie[now].son[s[i]-'0'];
}
}
trie[now].f=1;
}
int x=1;//这个就是有无前缀的标志，1代表的是没有，也就是需要输出yes的情况
void find(string s)
{
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'] !=0 )
{
now=trie[now].son[s[i]-'0'];
if(trie[now].f==1&&i!=len-1) //存在前缀字符串，并且不是自己本身
{
x=0;
return;
}
}
}
return ;
}
vector<string > vec;
string s;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int t;
cin>>t;
while(t--)
{
x=1;
num=0;
vec.clear();
memset(trie,0,sizeof(trie));
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s;
vec.push_back(s);
insert(s);
}
for(size_t i=0;i<n;i++)
{
find(vec[i]);
if(x==0)
{
cout<<"NO"<<endl;
break;
}
}
if(x)
{
cout<<"YES"<<endl;
}
}
return 0;
}
Immediate Decodability
思路：也是一样的找前缀。不同点在于输入，当输入'9'的时候表示输入结束。进行操作就好。
其实这题我觉得挺烦的，弄得我直接自闭。
//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int num=0;
struct node
{
int son[2];//01串，数组长度设置为2 就好
int f;
}trie[maxn];
string s[maxn];
void insert(string s)//插入操作没有任何改变
{
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'])
{
now=trie[now].son[s[i]-'0'];
}
else
{
trie[now].son[s[i]-'0']=++num;
now=trie[now].son[s[i]-'0'];
}
}
trie[now].f=1;
}
int find(string s)
{
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'])
{
now=trie[now].son[s[i]-'0'];
}
else
{
return 0;
}
}
//这个串已经被遍历完了，如果这时候的son还存在，那么就有一个别的串以它为前缀
if(trie[now].son[0]||trie[now].son[1])
{
return 1;
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
int n=0;
int bianhao=1;
int f=0;
while(cin>>s[n])
{
if(s[n]=="9")//解决问题
{
for(int i=0;i<n;i++)
{
f=find(s[i]);
if(f)//注意就是不一定需要全部查询的
{
break;
}
}
if(f)
{
printf("Set %d is not immediately decodable\n",bianhao++);
}
else
{
printf("Set %d is immediately decodable\n",bianhao++);
}
//记得重置，因为不重置，我WA了一下午。
n=0;
num=0;
f=0;
memset(trie,0,sizeof(trie));
}
else
insert(s[n++]);
}
return 0;
}The XOR Largest Pair
思路：首先你肯定是知道异或的计算的，就是二进制表示下，对于同一位，如果两个数不同，则该位置的异或值为1。相同为0。那么对于这个题，我们把每个数的二进制表示都放进去，然后去查询有没有不一样的不就行了。注意的是我们要从高位开始，并且如果没有不一样的，也不能退出，而要继续找下去。
//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=4e6+7;
const double pi=acos(-1);
using namespace std;
int num=1;
struct node
{
int son[2];//二进制数，数组开2就好
ll f;
}trie[maxn];
string fenjie(ll n)//分解为2进制数
{
string s="";
for(int i=0;i<32;i++)
{
s+=char((n&1)+48);
n>>=1;
}
//注意这个s可不是n的二进制表示。顺序反了
string ss="";
for(int i=31;i>=0;i--)
{
ss+=s[i];
}
return ss;
}
void insert(string s)//插入还是没变化
{
int len=32;
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'])
{
now=trie[now].son[s[i]-'0'];
}
else
{
trie[now].son[s[i]-'0']=num++;
now=trie[now].son[s[i]-'0'];
}
}
trie[now].f=1;
}
ll find(string s)
{
ll mx=0;//本次
int a[32];//这个就是两个数异或后得到的答案数字的二进制表示形式
int len=32;
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[!(s[i]-'0')])//要取反哦
{
now=trie[now].son[!(s[i]-'0')];
a[31-i]=1; //i越小，对应位置的值是越大的！
}
else
{
now=trie[now].son[s[i]-'0'];
a[31-i]=0;
}
}
ll q=1;
for(int i=0;i<len;i++)
{
mx+=q*a[i];
q<<=1;
}
return mx;
}
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int n;
cin>>n;
ll a;
string s;
ll mx=0;
for(int i=0;i<n;i++)
{
cin>>a;
s=fenjie(a);
insert(s);
mx=max(mx,find(s));
//cout<<a<<" "<<s<<endl;
}
cout<<mx<<endl;
return 0;
}
秘密消息Secret Message
思路:容易知道，需要输出的为：密码是多少条信息的前缀。那么这么一来又变成了模板了。这题的关键点就是信息长度和密码长度都未知的，他只搞到了部分，所以可以快乐YY，增加答案大小。
//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e6+7;
const double pi=acos(-1);
using namespace std;
int num=1;
struct node
{
int son[2];//二进制
int f;
int cnt;
}trie[maxn];
void insert(string s,int len)//因为题目给了你长度，多添加一个长度参数
{
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'])
{
now=trie[now].son[s[i]-'0'];
}
else
{
trie[now].son[s[i]-'0']=num++;
now=trie[now].son[s[i]-'0'];
}
if(i!=len-1)//值得注意的是这里！
trie[now].cnt++;//有信息经过了这里
}
trie[now].f++;//以这里为终点的信息 数量增加
}
int find(string s,int len)
{
int now=0;
int ans=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'])
{
now=trie[now].son[s[i]-'0'];
}
else//后面已经没有匹配的了，退出就好。
{
return ans;
}
if(trie[now].f) //存在以这里为终点的信息 ，这些信息后缀是不知道的。所以可以让他们成为答案中的一员。
{
ans+=trie[now].f;
}
}
return ans+trie[now].cnt;//最后再加上经过这里的信息就好。
}
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int n,m;
cin>>m>>n;
int q;
string s="";
char c;
//int mx=0;
for(int i=0;i<m;i++)
{
cin>>q;
s="";
for(int j=0;j<q;j++)
{
cin>>c;
s+=c;
}
insert(s,q);
}
for(int i=0;i<n;i++)
{
cin>>q;
s="";
for(int j=0;j<q;j++)
{
cin>>c;
s+=c;
}
cout<<find(s,q)<<endl;
}
//cout<<mx<<endl;
return 0;
}
还剩几个题，以为自己会了，结果发现自己好像解释不清楚。真是离谱，等我去琢磨一下。
写在最后：
本文是参考该文章 写的(因为我是看这该文学的，讲的很好，如果看完我的辣鸡文章你依然不能完全理解的话，可以去看看)
太菜了~现在看什么都是字典树。结果就是我2020JSCPC的H题T了无数发。从dp到爆搜。
京公网安备 11010502036488号