字典树_Trie树

title: 字典树(Trie树)
tags: 算法
date: 2022-11-29 10:59:22

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

简介

字典树，顾名思义，作用类似于字典，可以快速进行添加/删除/查询单词的操作。

前置知识

• 树

讲解

字典树本质是一棵树，根节点不存储信息。

字典树大概长这个样子:

上图中存储了以下信息：

hit
him
he
her
heap

可以看出，字典树本质是对相同前缀的部分进行压缩以达到节省空间的目的。

由此，我们可以写出插入的逻辑：

inline int mapping(char c){ // 映射函数
	return c-'a'; // 不同题目可能字母/符号不一样，就直接改变这里。
}

void add(char* s){
	int index = 1;
	for(int i=0;i<strlen(s);i++){ // 遍历每个字母
		if(!data[index][mapping(s[i])])// 如果不存在那个节点
			data[index][mapping(s[i])] = ++cnt; // 就新建一个
		index = data[index][mapping(s[i])]; // 继续往下走
	}
	vals[index] = ++wordcnt; // 标记这是一个单词
}

查询的逻辑和这个一模一样：

int query(char* s){
	int index = 1;
	for(int i=0;i<strlen(s);i++){ // 遍历每个字母
		if(!data[index][mapping(s[i])]) // 如果不存在那个节点
			return 0; // 退出并标记找不到
		index = data[index][mapping(s[i])]; // 继续往下走
	}
	return vals[index]; // 返回这个单词的id
}

例题

P2580 于是他错误的点名开始了

这道题比较简单，可以先练手。

P8306-【模板】字典树

这个也是差不多的模板题，需要对每个访问到的点+1

如果想要学习更多有关这个算法（字符串匹配）的内容，建议看看AC自动机。