字典树

• 0. 概述
• 1. 数据结构
• 2. 插入操作
• 3. 查询操作
• 4. 完整代码
  • 4.1. 字符数组
  • 4.2. 字符串

视频链接：F06 字典树(Trie)

0. 概述

• 是快速插入和查询字符串的多叉树结构，根节点编号为0，其余节点标识路径，还可以标记单词插入的次数，边表示字符。

1. 数据结构

const int N=1e5+5;
char s[N]; // 每次输入的字符串,N是每个单词的最大长度
int ch[N][26]; // ch[p][j]:从节点p沿着j这条边走到的子节点,边为26个小写字母映射值为0~25
int cnt[N]; // cnt[p]:以节点p结尾的单词的插入次数
int idx; // 遍历因子

2. 插入操作

• insert函数，插入单个单词并建立字典树

// s:单词(字符串)
void insert(char *s) {
	int p=0; // 根节点编号为0
	// 枚举字符串每个字符
	for(int i=0;s[i];i++) {
		int j=s[i]-'a'; // a~z映射到0~25
		// 如果这个字符不是儿子节点,创建儿子,p指针再走到儿子
		if(!ch[p][j]) ch[p][j]=++idx; // 节点编号+1
		// 如果这个字符是儿子节点,p指针走到儿子节点
		p=ch[p][j];
	}
	cnt[p]++; // 以节点p结尾的单词插入的次数+1 
}

3. 查询操作

• query函数，得到一个单词被插入的次数

// 查询某个单词出现的
int query(char *s) {
	int p=0; // 从根节点开始查
	// 扫描字符串
	for(int i=0;s[i];i++) {
		int j=s[i]-'a'; // 转换为映射值
		if(!ch[p][j]) return 0; // 如果找不到返回0
		// 有字母s[i],则走下来
		p=ch[p][j];
	}
	// 如果能走到词尾,则返回插入次数
	return cnt[p];
}

4. 完整代码

4.1. 字符数组

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 节点表示数字,边表示字符

const int N=1e5+5;
char s[N]; // 每次输入的字符串,N是每个单词的最大长度
int ch[N][26]; // ch[p][j]:从节点p沿着j这条边走到的子节点,边为26个小写字母映射值为0~25
int cnt[N]; // cnt[p]:以节点p结尾的单词的插入次数
int idx; // 遍历因子

// s:单词(字符串)
void insert(char *s) {
	int p=0; // 从根节点开始插
	// 枚举字符串每个字符
	for(int i=0;s[i];i++) {
		int j=s[i]-'a'; // a~z映射到0~25
		// 如果这个字符不是儿子节点,创建儿子,p指针再走到儿子
		if(!ch[p][j]) ch[p][j]=++idx; // 节点编号+1
		// 如果这个字符是儿子节点,p指针走到儿子节点
		p=ch[p][j];
	}
	cnt[p]++; // 以节点p结尾的单词插入的次数+1 
}

// 查询某个单词出现的
int query(char *s) {
	int p=0; // 从根节点开始查
	// 扫描字符串
	for(int i=0;s[i];i++) {
		int j=s[i]-'a'; // 转换为映射值
		if(!ch[p][j]) return 0; // 如果找不到返回0
		// 有字母s[i],则走下来
		p=ch[p][j];
	}
	// 如果能走到词尾,则返回插入次数
	return cnt[p];
}

int main() {
	int n;
	cin>>n;
	while(n--) {
		char op;
		scanf("%s%s",&op,s);
		if(op=='I') insert(s);
		else cout<<query(s)<<'\n';
	}
	return 0;
}

4.2. 字符串

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 节点表示数字,边表示字符

// 文件总长度不超过32K,所以总字符不超过:32K=32*1024
const int N=32*1024+10; 
char s[N]; // 每次输入的字符串,N是每个单词的最大长度
int ch[N][26]; // ch[p][j]:从节点p沿着j这条边走到的子节点,边为26个小写字母映射值为0~25
int cnt[N]; // cnt[p]:以节点p结尾的单词的插入次数
int idx; // 遍历因子

// s:单词(字符串)
void insert(string s) {
	int p=0; // 从根节点开始插
	// 枚举字符串每个字符
	for(int i=0;i<s.length();i++) {
		int j=s[i]-'A'; // a~z映射到0~25
		// 如果这个字符不是儿子节点,创建儿子,p指针再走到儿子
		if(!ch[p][j]) ch[p][j]=++idx; // 节点编号+1
		// 如果这个字符是儿子节点,p指针走到儿子节点
		p=ch[p][j];
	}
	cnt[p]++; // 以节点p结尾的单词插入的次数+1 
}

// 查询某个单词出现的
int query(string s) {
	int p=0; // 从根节点开始查
	// 扫描字符串
	for(int i=0;i<s.length();i++) {
		int j=s[i]-'a'; // 转换为映射值
		if(!ch[p][j]) return 0; // 如果找不到返回0
		// 有字母s[i],则走下来
		p=ch[p][j];
	}
	// 如果能走到词尾,则返回插入次数
	return cnt[p];
}

int main() {
//	while(scanf("%s",s)) {
//		insert(s);
//	}
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	while(cin>>s) {
		insert(s);
	}
	cout<<idx+1; // 加上根节点
	return 0;
}

打赏