前缀树Trie入门专题

前缀树Trie入门专题

Trie简介

从根节点开始,将单词的每一个字符依次插入树,相同的前缀不重复插入,这样形成的树我们称为前缀树或者叫字典树(Trie)。例如下面的前缀树:

img就是一个保存了8个单词信息(”A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”)。可以看出,树的最后一层一定是单词节点(即从根节点到孩子的字符的组合),但是单词节点不一定都在最后一层,这是因为存在相同的前缀。当然,我可以使用数组来另外标记单词节点。

前缀树是用空间换取时间的典型数据结构

建立Trie

我们使用tree[u][id]来表示在u节点下的id孩子的节点编号。id可以理解为当前字符到正整数的一个映射。我们通常使用字符在ASCII码中与字符a的”距离“来给字符编号。不管何时插入字符串,我们都会从树的根节点开始遍历,这样可以大幅度减少因前缀的重复而导致的空间的浪费,同时也达到了统计前缀数目的。我们使用sum[u]来表示节点编号为u的字符”出现“的次数。(这里的出现其实是代表相同前缀的次数)。最后,我们使用一个布尔数组标记单词节点。实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
inline void insert(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i]- 'a';
if (!tree[u][id]){
tree[u][id] = ++cnt;
}
sum[tree[u][id]]++;
u = tree[u][id];
}
vis[u] = 1;
}

当所有字符串插入完毕后,这颗树上总共有cnt个节点

Trie的查询操作

查询操作和插入操作十分相似,同时又因目的的不同而不同,这里只给出最基本的查询用法:给定前缀在字典中出现数目,如果没有就返回-1。

1
2
3
4
5
6
7
8
9
10
11
inline int search(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if (!tree[u][id]){
return -1;
}
u = tree[u][id];
}
return sum[u];
}

模板题1–HDU 1251

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

1
2
3
4
5
6
7
8
9
10
banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

1
2
3
4
2
3
1
0

题解

完全的模板题,甚至连一点技巧都没有。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000000 + 5;
int tree[maxn][30];
int val[maxn];
int cnt;

void insert(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if (!tree[u][id]){
tree[u][id] = ++cnt;
}
val[tree[u][id]]++;
u = tree[u][id];
}
}

int search(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if(!tree[u][id]){
return 0;
}
u = tree[u][id];
}
return val[u];
}

int main(){
char s[20];
while(gets(s) && strlen(s)){
insert(s);
}
while (gets(s)){
printf("%d\n",search(s));
}
return 0;
}

模板题2–HDU 2072

lily的好朋友xiaoou333最近很空,他想了一件没有什么意义的事情,就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。

Input

有多组数据,每组一行,每组就是一篇小文章。每篇小文章都是由小写字母和空格组成,没有标点符号,遇到#时表示输入结束。

Output

每组只输出一个整数,其单独成行,该整数代表一篇文章里不同单词的总数。

Sample Input

1
2
you are my friend
#

Sample Output

1
4

题解

求单词数目,就是统计总共多少个是单词节点,利用vis数组即可。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 5;
int tree[maxn][30];
bool vis[maxn];
int cnt;

inline void insert(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if (!tree[u][id]){
tree[u][id] = ++cnt;
}
u = tree[u][id];
}
vis[u] = 1;
}

inline void search(){
int ans = 0;
for (int i = 0;i <= cnt;++i){
if (vis[i]){
++ans;
}
}
printf("%d\n",ans);
}

int main(){
string tmp;
while (getline(cin,tmp) && tmp != "#"){
stringstream ss(tmp);
char s[50];
while (ss >> s){
insert(s);
}
search();
cnt = 0;
memset(tree,0,sizeof(tree));
memset(vis,0,sizeof(vis));
}
return 0;
}

模板题3–LuoguP2580

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉(详情请见已结束比赛CON900)。

题目描述

这之后校长任命你为特派探员,每天记录他的点名。校长会提供化学竞赛学生的人数和名单,而你需要告诉校长他有没有点错名。(为什么不直接不让他玩炉石。)

输入格式

第一行一个整数 n,表示班上人数。接下来 n 行,每行一个字符串表示其名字(互不相同,且只含小写字母,长度不超过 50)。第 n+2 行一个整数 m,表示教练报的名字。接下来 m 行,每行一个字符串表示教练报的名字(只含小写字母,且长度不超过 50)。

输出格式

对于每个教练报的名字,输出一行。如果该名字正确且是第一次出现,输出“OK”,如果该名字错误,输出“WRONG”,如果该名字正确但不是第一次出现,输出“REPEAT”。(均不加引号)

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
10
5  
a
b
c
ad
acd
3
a
a
e

输出 #1

1
2
3
OK
REPEAT
WRONG

说明/提示

对于 40%的数据,n≤1000,m≤2000;

对于 70%的数据,n≤10000,m≤20000;

对于 100%的数据, n≤10000,m≤100000。

题解

同上题,但是改为用vis表示是否点过名

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000000 + 5;

int tree[maxn][30];
int val[maxn];
int cnt;
bool vis[maxn];

inline void insert(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if (!tree[u][id]){
tree[u][id] = ++cnt;
}
val[tree[u][id]]++;
u = tree[u][id];
}
}

inline int search(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if (!tree[u][id]){
return -1;
}
u = tree[u][id];
}
if (!val[u]){
return -1;
}
if (vis[u]){
return 1;
}
vis[u] = 1;
return 0;
}

int main(){
char s[51];
int n;scanf("%d",&n);
for (int i = 0;i < n;++i){
scanf("%s",s);
insert(s);
}
scanf("%d",&n);
for (int i = 0;i < n;++i){
scanf("%s",s);
int ans = search(s);
if (ans == -1){
printf("WRONG\n");
}else if (ans == 0){
printf("OK\n");
}else{
printf("REPEAT\n");
}
}
return 0;
}

模板题4–POJ 2001

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, “carbohydrate” is commonly abbreviated by “carb”. In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, “carbohydrate” can be abbreviated to “carboh”, but it cannot be abbreviated to “carbo” (or anything shorter) because there are other words in the list that begin with “carbo”.

An exact match will override a prefix match. For example, the prefix “car” matches the given word “car” exactly. Therefore, it is understood without ambiguity that “car” is an abbreviation for “car” , not for “carriage” or any of the other words in the list that begins with “car”.

Input

The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

Output

The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

题解

输出可以辨别一个单词的最短前缀。可以容易的知道,当sum[i]大于1的时候,前缀是被共享的,即不能唯一确定一个单词。由于字典树的父亲节点的权值一定是大于等于其孩子节点的,所以我们从上往下找第一个sum[i]为1的i节点,此为最后输出。

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
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int maxn = 1e6 + 5;
char m[1050][25];
int tree[maxn][30];
int cnt;
int val[maxn];

inline void insert(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
if (!tree[u][id]){
tree[u][id] = ++cnt;
}
val[tree[u][id]]++;
u = tree[u][id];
}
}

inline void search(char s[]){
int u = 0;
for (int i = 0;s[i];++i){
int id = s[i] - 'a';
printf("%c",s[i]);
if (val[tree[u][id]] == 1){
return;
}
u = tree[u][id];
}
}

int main(){
int cot = 0;
while (~scanf("%s",m[cot++]));
for (int i = 0;i < cot;++i){
insert(m[i]);
}
for (int i = 0;i < cot;++i){
printf("%s ",m[i]);
search(m[i]);
printf("\n");
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×