浅谈字典树 2.0

chenzhixuan2010 · 2025-03-04 13:10:02 · 个人记录

Part 0 问题引入

先来看看一道题：

给定 n 个模式串 s_1, s_2, \dots, s_n 和 q 次询问，每次询问给定一个文本串 t_i，请回答 s_1 \sim s_n 中有多少个字符串 s_j 满足 t_i 是 s_j 的前缀。对于每一个测试点保证 1\leq n,q\leq10^5。

很明显，如果直接使用暴力大法，那么时间复杂度就会飞到 O(n^2q)，只要 n,q\geq10^3 就炸了。

聪明的同学可能会说：之前学过的 KMP 可以做到查询字符串。

但是 KMP 的每一次查询都是 O(n) 的，所以时间复杂度也只能缩到 O(nq)，显然还是过不去。

这时候我们发现，对于每一次询问，其实只要查询模式串的前缀而不是整个字符串。所以我们需要一个数据结构来处理这样的前缀问题。这个数据结构就是字典树。

Part 1 什么是字典树

字典树（Trie 树）是一种树形的数据结构。这种数据结构通常用于处理字符串的前缀。它可以用空间换时间，以达到快速完成插入、查询字符串的操作。

Part 2 字典树的结构（性质）

字典树上除根节点外的每一个节点都是一个字符。从根节点一直到某个节点 i 的所有节点的字符拼起来就代表了一个字符串。下面放一个例子：

~~个人认为之前的图不太好所以重画了一张~~

其中每个节点中间的数字是节点的编号，它们旁边的红色字母是他们的权值。

例如：root\rightarrow6\rightarrow7 代表的字符串是 NB，root\rightarrow6\rightarrow8\rightarrow9 代表的字符串是 NAI，而 root\rightarrow1\rightarrow2\rightarrow3\rightarrow5 代表的字符串是 LONG。

不难发现，如果选取一个节点 i，从 root 到 i 的最短路径上选取一个节点 j，那么从 root 到 j 代表的字符串是从 root 到 i 代表的字符串的前缀。

于是便可以通过操作实现字典树。下面我们用一道模板题来实现字典树。

Part 3 模板题 && 字典树的实现

模板题：P8306 【模板】字典树

题目描述

现在我们再次回到这道题：

给定 n 个模式串 s_1, s_2, \dots, s_n 和 q 次询问，每次询问给定一个文本串 t_i，请回答 s_1 \sim s_n 中有多少个字符串 s_j 满足 t_i 是 s_j 的前缀。

根据字典树的性质，我们可以把每一个字符串都塞入字典树中，然后对于每一个文本串查询即可。

题解

首先我们要把每一种字符转化成一个整数，方便存储。

int TrieGetnum(char x){
    if (x >= 'A' && x <= 'Z'){
        return x - 'A' + 1;
    }
    else if (x >= 'a' && x <= 'z'){
        return x - 'a' + 27;
    }
    else{
        return x - '0' + 53;
    }
}

接下来是插入操作。根据字典树的结构，我们需要从第一个字符开始一个一个往下找。如果能找到权值与该字符相同的节点就继续走，否则就新开一个子树，一直到遍历完成字符串。

void TrieInsert(string s){
    int a = 0,slen = s.size();
    for (int i = 0;i < slen;i++){
        int b = TrieGetnum(s[i]);
        if (Triet[a][b] == 0){
            Trieidx++; //这里就是找不到的情况
            Triet[a][b] = Trieidx;
        }
        a = Triet[a][b];
        Triecnt[a]++; //统计这棵子树有多少个儿子，以后有用
    }
}

接下来是查询操作。题目要我们求有多少个字符串满足要求。所以只要对于遍历到的最后一个节点，求出它的字数数量即可。这时候前面的 Triecnt 数组就派上用场了。当然如果在中间某一处无法往下走，直接返回 0 即可。

int TrieQuery(string s){
        int a = 0,slen = s.size();
        for (int i = 0;i < slen;i++){
            int b = TrieGetnum(s[i]);
            if (Triet[a][b] == 0){
                return 0; //遍历完前就找不到了
            }
            a = Triet[a][b];
        }
        return Triecnt[a];
    }

最后，由于本题是多组数据，所以我们还需要一个初始化函数。

void TrieInit(){
    for (int i = 0;i <= Trieidx + 3;i++){
        for (int j = 0;j <= 62;j++){ //这里的j的范围要看数据，这里是因为26+26+9=61，所以开了62
            Triet[i][j] = 0;
        }
    }
    for (int i = 0;i <= Trieidx + 3;i++){
        Triecnt[i] = 0;
    }
    Trieidx = 0;
}

最后把所有的代码加起来就可以得到最终代码了：

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Trie{
    int Trieidx = 0,Triet[3000005][65],Triecnt[3000005];
    void TrieInit(){
        for (int i = 0;i <= Trieidx + 3;i++){
            for (int j = 0;j <= 62;j++){
                Triet[i][j] = 0;
            }
        }
        for (int i = 0;i <= Trieidx + 3;i++){
            Triecnt[i] = 0;
        }
        Trieidx = 0;
    }
    int TrieGetnum(char x){
        if (x >= 'A' && x <= 'Z'){
            return x - 'A' + 1;
        }
        else if (x >= 'a' && x <= 'z'){
            return x - 'a' + 27;
        }
        else{
            return x - '0' + 53;
        }
    }
    void TrieInsert(string s){
        int a = 0,slen = s.size();
        for (int i = 0;i < slen;i++){
            int b = TrieGetnum(s[i]);
            if (Triet[a][b] == 0){
                Trieidx++;
                Triet[a][b] = Trieidx;
            }
            a = Triet[a][b];
            Triecnt[a]++;
        }
    }
    int TrieQuery(string s){
        int a = 0,slen = s.size();
        for (int i = 0;i < slen;i++){
            int b = TrieGetnum(s[i]);
            if (Triet[a][b] == 0){
                return 0;
            }
            a = Triet[a][b];
        }
        return Triecnt[a];
    }
}

using namespace Trie;
void slove(){
    TrieInit();
    int n,q;
    cin>>n>>q;
    string s;
    for (int i = 1;i <= n;i++){
        cin>>s;
        TrieInsert(s);
    }
    for (int i = 1;i <= q;i++){
        cin>>s;
        cout<<TrieQuery(s)<<'\n';
    }
    return ;
}

signed main(){
    int t;
    cin>>t;
    while (t--){
        slove();
    }
    return 0;
}

Part 4 例题

~~双倍经验：P10470~~

洛谷 P2580 于是他错误的点名开始了 \texttt{题解}
洛谷 P3879 [TJOI2010] 阅读理解 \texttt{题解}

Part 5 题单 / 比赛

链接：https://www.luogu.com.cn/contest/234077