Trie

　　1、基本概念

  字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。

　　2、基本性质

  根节点不包含字符，除根节点外的每一个子节点都包含一个字符
  从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
  每个节点的所有子节点包含的字符都不相同

　　3、应用场景

  典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。

　　4、优点

  利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。

构建方式

首先定义一个结构体，包含该节点的信息，和通向下方节点的Next数组，一般由字符串中的不同字符个数决定

struct node{
    int Next[26];
    int cnt;
}a[1000005]; //大小一般为n * m log n

然后需要写一个add函数，用于将新的字符串加入到树中

void add(){
    int len=strlen(s+1);
    int now=0;
    for (int i=1;i<=len;++i){
        if (a[now].Next[s[i]-'a']==0){
            cnt++;
            a[now].Next[s[i]-'a']=cnt;
            now=cnt;
        }else now=a[now].Next[s[i]-'a'];
        if (i==len) a[now].cnt++;
    }
}

以及find函数，用于查找一个字符串的相关信息

void find(){
    int len=strlen(s+1);
    int now=0,ans=0;
    for (int i=1;i<=len;++i){
        if (a[now].Next[s[i]-'a']==0) break;
        else now=a[now].Next[s[i]-'a'];
        ans+=a[now].cnt;
    }
    printf("%d\n",ans);
}

例题

前缀统计

题面

思路

非常典型的trie树

#include <bits/stdc++.h>
using namespace std;

struct node{
    int Next[26];
    int cnt;
}a[1000005];
int cnt,n,m;
char s[1000005];

void add(){
    int len=strlen(s+1);
    int now=0;
    for (int i=1;i<=len;++i){
        if (a[now].Next[s[i]-'a']==0){
            cnt++;
            a[now].Next[s[i]-'a']=cnt;
            now=cnt;
        }else now=a[now].Next[s[i]-'a'];
        if (i==len) a[now].cnt++;
    }
}

void find(){
    int len=strlen(s+1);
    int now=0,ans=0;
    for (int i=1;i<=len;++i){
        if (a[now].Next[s[i]-'a']==0) break;
        else now=a[now].Next[s[i]-'a'];
        ans+=a[now].cnt;
    }
    printf("%d\n",ans);
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        add();
    }
    for (int i=1;i<=m;++i){
        scanf("%s",s+1);
        find();
    }
    return 0;
}

最大异或数字对

题目

思路

将已有的数字按照二进制构建trie树，每读入一个数，查找于它xor值最大是多少，采用贪心策略，尽可能让高位不同

#include <bits/stdc++.h>
using namespace std;

int n,m,tmp,cnt,ans;

struct node{
    int Next[2];
}t[31*100000+5];

void add(){
    int now=0;
    for (int i=30;i>=0;--i){
        int a=(tmp>>i)&1;
        if (t[now].Next[a]==0) t[now].Next[a]=++cnt;
        now=t[now].Next[a];
    }
}

int find(){
    int now=0,ans=0;
    for (int i=30;i>=0;--i){
        int a=(tmp>>i)&1;
        ans<<=1;
        if (t[now].Next[a^1]) now=t[now].Next[a^1],ans|=1;
        else now=t[now].Next[a];
    }
    return ans;
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        scanf("%d",&tmp);
        add();
        ans=max(ans,find());
    }
    cout<<ans<<endl;
    return 0;
}

最大异或路径

题面

思路

只要想到任意两点A,B的XOR值=(A到根的距离)XOR(B到根的距离)，即可转化为上面一个问题

#include <bits/stdc++.h>
using namespace std;

int n,m,tmp,cnt,cn,ans;
int head[100005],d[100005],Next[200005],a[200005],en[200005],v[200005];

struct node{
    int Next[2];
}t[31*100000+5];

void add(){
    int now=0;
    for (int i=30;i>=0;--i){
        int a=(tmp>>i)&1;
        if (t[now].Next[a]==0) t[now].Next[a]=++cnt;
        now=t[now].Next[a];
    }
}

int find(){
    int now=0,ans=0;
    for (int i=30;i>=0;--i){
        int a=(tmp>>i)&1;
        ans<<=1;
        if (t[now].Next[a^1]) now=t[now].Next[a^1],ans|=1;
        else now=t[now].Next[a];
    }
    return ans;
}

void add(int st,int en,int vi){
    cn++;
    Next[cn]=head[st];
    head[st]=cn;
    a[cn]=en;
    v[cn]=vi;
}

void bl(int st,int ans,int f){
    d[st]=ans;
    for (int i=head[st];i!=-1;i=Next[i]){
        if (a[i]!=f) bl(a[i],v[i]^ans,st);
    }
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) head[i]=-1;
    for (int i=1;i<=n-1;++i){
        int a,b,v;
        scanf("%d %d %d",&a,&b,&v);
        add(a,b,v);
        add(b,a,v);
    }
    bl(1,0,0);
    for (int i=1;i<=n;++i){
        tmp=d[i];
        add();
        ans=max(ans,find());
    }
    printf("%d\n",ans);
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/81/