trie树也叫字典树,前缀树
字典树（Trie）有如下几条性质
- 结点不存值,依靠树枝(边)存值
- 从根节点到某一处标记点为一个单词
- 每个结点到其子节点的边上的值各不相同
- 插入和查询复杂度均为O(mn),m为字符串个数,n为字符串平均长度
- 树深度由最长字符串决定
依次便可做出trie树的结点结构
struct trie{
int cnt=0;
bool word=0;
trie * son[26]={0};
};
让我们依次价绍这几个成员的含义
cnt这条边上有几个单词经过,即有多少指定的前缀相同的单词word从根节点这个结点是否是一个单词son[26]其子节点的地址;
依据其基本性质和结构体成员,写出构造函数如下
void make()
{
string s;
cin>>s;
int lo=s.lenth();
trie * now=root;
for(int i=0;i<lo;i++){
if(now->son[s[i]-'a']) now = now->son[s[i]-'a'];
else {
now->son[s[i]-'a']=new trie;
now=now->son[s[i]-'a'];
}
now->cnt++;
}
now->word=1;
}
首先读入一个字符串,得到其长度,并将查询指针调至根节点
这时从字符串第一个字符开始查询该字符是否已经存过
如果存过则将查询指针所在结点的cnt++,并移至该节点,如果未存过,则申请一个新结点连接到相应位置上
直到最后一个结点,将最后一个结点中的word标记改为1
根据trie树性质同时可写出查询函数
void check()
{
char s[55];
scanf("%s",s);
int lo=strlen(s),i;
trie * now=root;
for(i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
continue;
}
else {
printf("NO
");
break;
}
}
if(i == lo){
printf("YES
");
}
}
首先读入需要查询的字符串,按生成树的方式判断是否存过某字符,若存过,则进入所存结点
若未存过,则break,防止访问空指针,若只判断是否含有某前缀,则上述函数可完成,查询单词时,可将最后一处判断改为
if(i == lo && now->word){
printf("YES
");
}
else{
printf("NO
");
}
即当循环结束,字符串在树中时,判断是否这个字符串是整个单词
当树生成时,自动实现字符串的排序
可用递归实现
同时可用递归实现树的删除
与hash比较
Trie 的强大之处就在于它的时间复杂度。O(n)，与 Trie 中保存了多少个元素无关。
Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(n) ，而且还有可能冲突的问题
Trie 的缺点是空间消耗很高。
trie树拓展
AC自动机
为trie树上的KMP,留于KMP处详解
后缀树
可实现后缀自动机
基数数
将二进制数拆成几个2位数或几个4位数,按trie树方式存入
好像没什么卵用
trie树例题:
洛谷 2580
题解
#include<cstdio>
#include<cstring>
using namespace std;
struct trie{
bool check=0;
bool word=0;
trie * son[26]={0};
};
trie *root;
void make()
{
char s[55];
scanf("%s",s);
int lo=strlen(s);
trie * now=root;
for(int i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
continue;
}
else {
now->son[s[i]-'a']=new trie;
now=now->son[s[i]-'a'];
}
}
now->word=1;
}
void check()
{
char s[55];
scanf("%s",s);
int lo=strlen(s),i;
trie * now=root;
for(i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
continue;
}
else {
printf("WRONG
");
break;
}
}
if(i == lo && now->word){
if(now->check){
printf("REPEAT
");
}
else{
printf("OK
");
now->check=1;
}
}
}
int main()
{
root = new trie;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
make();
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
check();
}
return 0;
}
codevs 4189
题解:
#include<cstdio>
#include<cstring>
using namespace std;
struct trie{
trie * son[26];
};
trie *root;
void make()
{
char s[55];
scanf("%s",s);
int lo=strlen(s);
trie * now=root;
for(int i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
continue;
}
else {
now->son[s[i]-'a']=new trie;
now=now->son[s[i]-'a'];
}
}
}
void check()
{
char s[55];
scanf("%s",s);
int lo=strlen(s),i;
trie * now=root;
for(i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
continue;
}
else {
printf("NO
");
break;
}
}
if(i == lo){
printf("YES
");
}
}
int main()
{
root = new trie;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
make();
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
check();
}
return 0;
}
#include<cstdio>
#include<cstring>
using namespace std;
struct trie{
int cnt=0;
trie * son[26]={0};
};
trie a;
trie *root=&a;
void make()
{
char s[15];
scanf("%s",s);
int lo=strlen(s);
trie * now=root;
for(int i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
now->cnt++;
continue;
}
else {
now->son[s[i]-'a']=new trie;
now=now->son[s[i]-'a'];
now->cnt++;
}
}
}
void check()
{
char s[55];
scanf("%s",s);
int lo=strlen(s),i;
trie * now=root;
for(i=0;i<lo;i++){
if(now->son[s[i]-'a']){
now = now->son[s[i]-'a'];
continue;
}
else {
printf("0
");
break;
}
}
if(i == lo){
printf("%d
",now->cnt);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
make();
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
check();
}
return 0;
}