简介

一种高效地「存储」和「查找」字符串集合的数据结构。对于Trie树来说只能有两种操作：「插入」和「查找」。

一般这种题的元素种类不会太多（全是小写字母或全是大写字母或只有数字），并且字符串长度不会太大（一般不超过 $1e5$ ）。它的建树时间复杂度为 $O(n)$ ， $n$ 是字符串个数。

「直观展示存储方式」：

假设有：abcdef，abdef，aced，bcdf，cdaa，bcdc，cda。存储方式：

image-20240305112300709

可以看到，存储每个字符串时，都会从根节点遍历，寻找共同的部分，如果遇到不同字符了，就新建一颗子树。

同时也要注意，每一个单词的结尾都要打上标记，如上图 cdaa 和 cda，如果没有标记的话，就会造成 cda 这个单词的遗漏。可以用布尔数组来记录，也可以用整型数组。其中第i位表示idx为i的节点作为字符串结尾是否出现或出现的次数。

查找时：查找一个单词必须要先判断路径上每个节点是否存在，并且最后一个字母是否有标记。

例题

下面第一题就是纯纯模版题（没有一点弯弯绕绕），因此不总结模版了。

Trie字符串统计

「题目描述」：

维护一个字符串集合，支持两种操作：

  1. “I x”：向集合中插入一个字符串x；
  2. “Q x”：询问一个字符串在集合中出现了多少次。

共有N个操作，输入的字符串总长度不超过$10^5$，字符串仅包含小写英文字母。

「输入格式」：

第一行包含整数$N$，表示操作数。

接下来$N$行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。

「输出格式」：

对于每个询问指令”Q x”，都要输出一个整数作为结果，表示$x$在集合中出现的次数。

每个结果占一行。

「数据范围」：

$1 \le N \le 2*10^4$

「输入样例」：

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

「输出样例」：

1
2
3
1
0
1

「实现代码」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int N = 1e5+5;
int son[N][26]; // 表示节点的子节点（题目中全是小写字母，因此最多26个子节点）
int cnt[N]; // 表示以该节点作为结尾的单词的格个数（也是标记）
int idx; // 当前用到的编号（和数组实现链表时含义相同），这里下标是0的点即是根节点又是空节点
char s[N]; // 读入的字符串

void insert(char str[]) {
	int p = 0; // 初始父节点为根节点编号为0
	for (int i = 0; str[i]; ++i) { // 字符串结尾是0
		int u = str[i] - 'a'; // 操作下一个字符，将其作为子节点
		if (!son[p][u]) son[p][u] = ++idx; // 如果子节点不存在就创建,注意先加在赋值（不能写成idx++）
		p = son[p][u]; // 然后让新的节点作为下一步的父节点
	}

	cnt[p] ++; // p最终就是最后一个字母，表示单词的结尾
}

int query(char str[]) {
	int p = 0;
	for (int i = 0; str[i]; ++i) {
		int u = str[i] - 'a'; // 操作下一个字符，将其作为子节点
		if (!son[p][u]) return 0; // 如果该节点不存在，表示没有查询的单词，直接返回0
		p = son[p][u]; // 继续往子节点走
	}

	return cnt[p]; // 最终p就是该单词的最后一个字母，返回以该字母结尾的单词的个数
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		char op[2];
		cin >> op >> s;
		if (*op == 'I') insert(s);
		else cout << query(s) << endl;
	}

	return 0;
}

当然操作的时候不一定要用char str[]，用string也是可以的。用string实现的模版：P2580 于是他错误的点名开始了

P8306 【模板】字典树

这道题虽然写着是模版题，但是还是要稍微转变一点点。

「题目链接」：https://www.luogu.com.cn/problem/P8306

「思路」：

这道题是要统计以某一个字符串为前缀的字符串的个数，因此需要改变一下打标记的方式，在每一次遍历到一个节点的时候，就给该节点的标记数量加一，插入完成后，该店的标记数量就表示经过该节点的单词数。

这道题的元素种类比较多，大小写字母和数字都有，因此这里多写了一个函数(get_idx())，将这些字符映射到0～61范围内(A~Z：0~25，a~z：26~51，0~9：52~61)。

注意：这道题会输入多组样例，每次执行样例前要先初始化。

「实现代码」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>

using namespace std;

const int N = 3e6+5;
int t, n, m;
int son[N][62], cnt[N], idx;
char s[N];

void init() {
	for (int i = 0; i <= idx; ++i)
		for (int j = 0; j <= 62; ++j)
			son[i][j] = 0;
	for (int i = 0; i <= idx; ++i) cnt[i] = 0;
	idx = 0;
}

int get_idx(char a) {
	if (a >= 'A' && a <= 'Z') return a - 'A';
	if (a >= 'a' && a <= 'z') return a - 'a' + 26;
	return a - '0' + 52;
}

void insert(char str[]) {
	int p = 0;
	for (int i = 0; str[i]; ++i) {
		int u = get_idx(str[i]);
		if (!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
		cnt[p] ++; // 这道题要给每个经过节点的cnt增加，表示通过该节点的单词数量
	}
}

int query(char str[]) {
	int p = 0;
	for (int i = 0; str[i]; ++i) {
		int u = get_idx(str[i]);
		if (!son[p][u]) return 0;
		p = son[p][u];
	}
	return cnt[p];
}

void solve() {
	init();

	cin >> n >> m;
	while (n -- ) {
		cin >> s;
		insert(s);
	}

	while (m -- ) {
		cin >> s;
		cout << query(s) << endl;
	}
}

int main() {
	cin >> t;
	while (t--) solve();

	return 0;
}

提交通过：

截屏2024-03-05 16.16.29

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

「题目链接」：https://www.luogu.com.cn/problem/P2580

「思路」：

这道题会就是基础模版题了，它只需要判断是否有那个字符串即可，即判断cnt[尾]是否大于1。

但是有个点是输出会有REPATE，我这里是用的unordered_map<string, string>来存状态，当一个名字重复查的时候可以很快地返回”REPEATE”或者”WRONG”。

因为用到了unordered_map,它不能定义为char数组，因此使用string，因此这一算是一个用string实现的模版。

「实现代码」：

这里所以下N的取值，可以看到题目中的数据范围：要插入的字符串个数最大为$10^4$，每个字符串最长不超过50（可取50），因此两个相乘，最多有$5*10^5$个节点。因此这里N取 5e5+5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 5e5+5;
int n, m;
int son[N][26], idx;
bool st[N]; // 单词结尾的标记，true表示是结尾，false表示不是结尾
unordered_map<string, string> mp; // 用于存单词的状态，如：mp['ab'] = "OK"，表示单词ab的查询结果为"OK"
string s;

void insert(string str) {
	int p = 0;
	for (char c: str) {
		int u = c - 'a';
		if (!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}

	st[p] = true;
}

bool query(string str) {
	int p = 0;
	for (char c: str) {
		int u = c - 'a';
		if (!son[p][u]) return false; // 没有子节点，更不会有该单词
		p = son[p][u];
	}

	return st[p];
}

int main() {
	cin >> n;
	while (n -- ) {
		cin >> s;
		insert(s);
	}

	cin >> m;
	while (m -- ) {
		cin >> s;
		if (mp.count(s)) {
			if (mp[s] == "OK") puts("REPEAT"); 
			else puts("WRONG");
		} else {
			bool res = query(s);
			if (res) mp[s] = "OK";
			else mp[s] = "WRONG";

			cout << mp[s] << endl;
		}
	}

	return 0;
}

提交通过：

截屏2024-03-05 16.43.13