专栏文章

浅谈字典树 2.0

cchenzhixuan2010
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq20m1n
此快照首次捕获于
2025/12/03 21:40
3 个月前
此快照最后确认于
2025/12/03 21:40
3 个月前
查看原文

Part 0 问题引入

先来看看一道题：
给定 nn 个模式串 s1,s2,…,sns_1, s_2, \dots, s_n 和 qq 次询问，每次询问给定一个文本串 tit_i，请回答 s1∼sns_1 \sim s_n 中有多少个字符串 sjs_j 满足 tit_i 是 sjs_j 的前缀。对于每一个测试点保证 1≤n,q≤1051\leq n,q\leq10^5。
很明显，如果直接使用暴力大法，那么时间复杂度就会飞到 O(n2q)O(n^2q)，只要 n,q≥103n,q\geq10^3 就炸了。
聪明的同学可能会说：之前学过的 KMP 可以做到查询字符串。
但是 KMP 的每一次查询都是 O(n)O(n) 的，所以时间复杂度也只能缩到 O(nq)O(nq)，显然还是过不去。
这时候我们发现，对于每一次询问，其实只要查询模式串的前缀而不是整个字符串。所以我们需要一个数据结构来处理这样的前缀问题。这个数据结构就是字典树。

Part 1 什么是字典树

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

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

字典树上除根节点外的每一个节点都是一个字符。从根节点一直到某个节点 ii 的所有节点的字符拼起来就代表了一个字符串。下面放一个例子：
个人认为之前的图不太好所以重画了一张
其中每个节点中间的数字是节点的编号，它们旁边的红色字母是他们的权值。
例如：root→6→7root\rightarrow6\rightarrow7 代表的字符串是 NB，root→6→8→9root\rightarrow6\rightarrow8\rightarrow9 代表的字符串是 NAI，而 root→1→2→3→5root\rightarrow1\rightarrow2\rightarrow3\rightarrow5 代表的字符串是 LONG。
不难发现，如果选取一个节点 ii，从 rootroot 到 ii 的最短路径上选取一个节点 jj，那么从 rootroot 到 jj 代表的字符串是从 rootroot 到 ii 代表的字符串的前缀。
于是便可以通过操作实现字典树。下面我们用一道模板题来实现字典树。

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

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

题目描述

现在我们再次回到这道题：
给定 nn 个模式串 s1,s2,…,sns_1, s_2, \dots, s_n 和 qq 次询问，每次询问给定一个文本串 tit_i，请回答 s1∼sns_1 \sim s_n 中有多少个字符串 sjs_j 满足 tit_i 是 sjs_j 的前缀。
根据字典树的性质，我们可以把每一个字符串都塞入字典树中，然后对于每一个文本串查询即可。

题解

首先我们要把每一种字符转化成一个整数，方便存储。
CPP
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;
	}
}
接下来是插入操作。根据字典树的结构，我们需要从第一个字符开始一个一个往下找。如果能找到权值与该字符相同的节点就继续走，否则就新开一个子树，一直到遍历完成字符串。
CPP
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 数组就派上用场了。当然如果在中间某一处无法往下走，直接返回 00 即可。
CPP
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];
	}
最后，由于本题是多组数据，所以我们还需要一个初始化函数。
CPP
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;
}
最后把所有的代码加起来就可以得到最终代码了：
CPP
#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
  1. 洛谷 P2580 于是他错误的点名开始了 题解\texttt{题解}
  2. 洛谷 P3879 [TJOI2010] 阅读理解 题解\texttt{题解}

Part 5 题单 / 比赛

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...