字典树
字典树，因为它的搜索快捷的特性被单词搜索系统使用，故又称单词查找树。它是一种树形结构的数据结构。之所以快速，是因为它用空间代替了速度。
性质
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2.从根节点到某一个节点，路径上经过的字符连接起来，就是该节点对应的字符串；
3.每个节点的所有子节点包含的字符都不相同。
应用
1.字符串的快速查找：
给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
2.串排序：
给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出用字典树进行排序，采用数组的方式创建字典树，这棵树的每个节点的所有儿子很显然地按照其字母大小排序,对这棵树进行先序遍历即可。
3.最长公共前缀：
对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的节点的公共祖先个数，于是，问题就转化为最近公共祖先问题。
算法实现
1
2
3
4
5
6
|
struct Node{
Node * ch[26];
int num;
};
|
1
2
3
4
5
6
| Node a[N], * root, * ap;
Node * newnode(){
memset(ap->ch, 0, sizeof(ap->ch));
ap->num = 0;
return ap++;
}
|
向字典树中插入一个字符串：
1
2
3
4
5
6
7
8
9
10
11
| void Insert(char * s){
Node * cur = root;
cur->num++;
while(* s != '\0'){
int t = * (s++) - 'a';
if(cur->ch[t] == NULL)
cur->ch[t] = newnode();
cur = cur->ch[t];
cur->num++;
}
}
|
在 main 函数中，要初始化和清空字典树：
1
2
| ap = a;
root = newnode();
|
例题
模板题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
45
46
47
48
49
50
51
52
53
54
55
| #include <cstdio>
#include <cstring>
using namespace std;
const int N = 500000;
struct node{
node * ch[26];
int num;
}a[N], * root;
char s[11];
int p = 0;
node * newNode(){
memset(a[p].ch, 0, sizeof(a[p].ch));
a[p].num = 0;
return &a[p++];
}
void Insert(char * s){
node * cur = root;
cur->num++;
while(* s != '\0'){
int t = * (s++) - 'a';
if(cur->ch[t] == NULL)
cur->ch[t] = newNode();
cur = cur->ch[t];
cur->num++;
}
}
int getans(char * s){
node * cur = root;
while(* s != '\0'){
int t = * (s++) - 'a';
if(cur->ch[t] == NULL) return 0;
cur = cur->ch[t];
}
return cur->num;
}
int main(){
root = newNode();
gets(s);
while(s[0] != '\0'){
Insert(s);
gets(s);
}
while(~scanf("%s", s)){
printf("%d\n", getans(s));
}
return 0;
}
|
模板题2