Trie 从入门到入土

lkjzyd20 · 2025-04-07 17:00:01 · 算法·理论

Tags: 字典树,Trie 字符串

字典树

前言

字典树，形如其名，像字典的树。

核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它支持快速存储字符集合，快速查询字符集合，快速修改字符集合是否存在。

如何构建

先放一张图

我们可以发现字典树的性质

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。

• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

• 每个节点的所有子节点包含的字符都不相同。

那么，请你画出下面字符串的字典树

• \tt ba
• \tt bag
• \tt ban
• \tt bat
• \tt bi
• \tt big
• \tt bil
• \tt bit

应该就是这个样子：

我们使用 C++ 代码来构建它：

//son[][]存储子节点的位置，分支最多26条；
//cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26],cnt[N],idx;
char str[N];
int change(char s){return s-'a';}
void insert(char *str){
    int p=0;  //指向当前节点
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]); //将字母转化为数字
        if(!son[p][u])son[p][u]=++idx;   //该节点不存在，创建节点
        p=son[p][u];  //使 p 指向下一个节点
    }
    ++cnt[p];  //结束时的标记，也是记录以此节点结束的字符串个数
}

查询其实也差不多：

int query(char *str){
    int p=0; //指向当前节点
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]); //将字母转化为数字
        if(!son[p][u])return 0;  //该节点不存在，即该字符串不存在
        p=son[p][u]; //使 p 指向下一个节点
    }
    return cnt[p];  //返回字符串出现的次数
}

如何删掉呢？

void del(char *str){
    int p=0; //指向当前节点
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]); //将字母转化为数字
        if(!son[p][u])return 0;  //该节点不存在，即该字符串不存在
        p=son[p][u]; //使 p 指向下一个节点
    }
    --cnt[p];  //减少这个字符串出现的次数
}

然后做

• P10470 前缀统计
• PKU2503 Babelfish
• Poj3630 Phone List
• HDU1251 统计前缀
• Shortest Prefixes

35 分钟吧，不会做的可以问我。

Trie 的批量删除（度熊查单词）

百度的题目，挺新奇的，需要另一种思路维护删除操作（当然还有其他思路）。

void del(char *str){
    int p=0;
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]);
        if(!son[p][u])return;
        p=son[p][u];
    }// 查询是否有该前缀
    p=0;
    int t;
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]);
        t=p;
        p=son[p][u];
        --cnt[p];//前缀减去
    }
    son[t][change(str[(int)strlen(str)-1])]=0;//该点清零
}

另外，我发现网上的题解大多是错的（迷惑行为）？？？

原因在于大多数题解是直接删掉了所有节点，代码是这样的：

void del(char *str){
    int p=0;
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]);
        if(!son[p][u])return;
        p=son[p][u];
    }
    int ans=cnt[p];p=0;
    rep(i,0,(int)strlen(str)-1){
        int u=change(str[i]);
        cnt[p]-=ans;
        p=son[p][u];
    }
    rep(u,0,25)son[p][u]=0;
}

这会导致下一次无法继续扫到该节点，所以会出错。

[USACO08DEC] Secret Message G

给出 N 个 \tt01 串和 M 个 \tt 01串，问这 M 个串的每一个串中满足和这 N 个串其中的一个串有着相同的前缀（前者是后者的前缀或后者是前者的前缀）的数量。

思路：稍微的变形，我们记录一个 end_p 表示有多少个以当前节点为结尾的字符串，再记录一个 cnt_p 表示路过这个节点的字符串有多少个，注意，结尾和路过不要同时记录，然后查询时直接统计 end_p 和 cnt_p 即可。

#include <bits/stdc++.h>
// #define int long long 
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=1000010;
int son[N][2],cnt[N],ed[N],idx;
int s[N];
void insert(int *s){
    int p=0;  
    rep(i,1,s[0]){
        int u=s[i]; 
        if(!son[p][u])son[p][u]=++idx;   
        if(p)++cnt[p];
        p=son[p][u];  
    }
    ++ed[p];
}
int query(int *s){
    int p=0,sum=0; 
    rep(i,1,s[0]){
        int u=s[i];
        if(!son[p][u])return sum;
        p=son[p][u]; 
        sum+=ed[p];
    }
    return sum+cnt[p];  
}
main(){
    int n,m;cin>>n>>m;
    rep(i,1,n){
        cin>>s[0];
        rep(j,1,s[0])cin>>s[j];
        insert(s);
    }
    rep(i,1,m){
        cin>>s[0];
        rep(j,1,s[0])cin>>s[j];
        cout<<query(s)<<'\n';
    }
}

为什么记录这题呢，因为这个题它同时考察了两种最常用的标记方法，挺典型的。

然后思维题：SP694，思考一下 trie 的本质。

模拟题：子串统计

给你一个长度为 N 的 01 字符串，然后问你在它的所有子串中，那些出现次数大于 1 次的子串的出现次数。

输出的顺序按子串本身的字典序，例如假设 01 这个子串出现 3 次，011 这个子串出现 2 次，则先输出 3 再输出 2

思路：暴力统计，dfs 输出即可

时限为 20 分钟。

开始进阶

01-trie 树可以用来维护一堆数字的异或和，支持修改（删除+重新插入），和全部维护值加一。

友情提示：下面题目难度为 ????

The XOR Largest Pair

这题好像是蓝书的例题，嗯，确实挺典型的。

在给定的 N 个整数 A_1,A_2,…,A_N 中选出两个进行异或运算，得到的结果最大是多少？

我们先把每个数给转化为 32 位二进制数，接着思考如何选。我们可以发现，只有二进制数位数越多才能选，然后前面异或时尽量都为 \tt1。则使 A_i 与其异或值最大的整数一定是高位至低位与 A_i 有尽可能多的不同位（使异或结果可以尽可能多地获得 \tt1）。

字典树开数组注意计算（纯靠运气）！！！

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=10000010;
int n,A[N];
int son[N][2],idx,ans;
void insert(int x){
    int p=0;
    per(i,31,0){
        int k=(x>>i)&1;
        if(!son[p][k])son[p][k]=++idx;
        p=son[p][k];
    }
}
int query(int x){
    int p=0,ans=0;
    per(i,31,0){
        int k=(x>>i)&1;
        if(!son[p][k^1])p=son[p][k];
        else p=son[p][k^1],ans^=(1<<i);
    }
    return ans;
}
main()
{
    cin>>n;
    rep(i,1,n){
        cin>>A[i];
        insert(A[i]);
    }
    rep(i,1,n){
        ans=max(ans,query(A[i]));
    }
    cout<<ans;
    return 0;
}

Pku3764 The xor-longest Path

给定一棵 n 个点的带权树，求树上最长的异或和路径。

思路：其实跟上一题差不多，预处理出每一个节点到根的异或和就可以了。

「一本通 2.3 例 3」Nikitosh 和异或

求出两个不同区间 A,B，使得 A 的异或和加上 B 的异或和最大。

首先，我们知道区间 [l,r] 的异或和可以表示为 [1,l] \oplus [1,r]，那么我们可以设 S1_i 表示区间 [1,i] 的最大异或和，S2_i 表示区间 [i,n] 的最大异或和，用 Trie 维护一下即可。

main(){
    cin>>n;
    rep(i,1,n){
        cin>>A[i];
        insert(A[i]);
        s1[i]=max(s1[i-1],query(A[i]));
    }
    memset(son,0,sizeof 0);
    idx=0;
    per(i,n,1){
        insert(A[i]);
        s2[i]=max(s2[i+1],query(A[i]));
    }
    rep(i,1,n-1){
        ans=max(ans,s1[i]+s2[i+1]);
    }
    cout<<ans;
    return 0;
}

[JOI Open 2016] 销售基因链 / Selling RNA Strands

建议去 luogu 交，有全部数据。

题意：给定 n 个文本串 S_i，有 m 次询问，每次给定两个字符串 P,Q，求有多少个文本串同时包含前缀 P 和后缀 Q。