首页 > 代码库 > 字典树

字典树

2024-10-16 15:07:02   213人阅读

字典树可以用来快速查找字符串前缀，当然，适当的变下形就可以解决需要很多了。

技术分享

从根节点开始，每遇见一个红点就可以组成一个单词。

节点的建立：

　　

 1 struct Nod{
 2     bool is;
 3     Nod *next[26];
 4     Nod(){
 5         is = false;
 6         for(int i = 0; i < 26; i ++){
 7             next[i] = NULL;
 8         }
 9     }
10 };

插入：

1 void mkTrie(Nod *root,char *s){
2     Nod*p = root;
3     for(int i = 0; s[i]; i ++){
4         int a = s[i] - ‘0‘;
5         if(p->next[a]==NULL)p->next[a] = new Nod;
6         p = p->next[a];
7     }
8     p->is = true;
9 }

删除：（很多题目有很多组数据，如果不删除释放空间的话，很容易导致Memory Limit Exceeded）

 1 void deleTrie(Nod *p){
 2     if(p == NULL) return;
 3     for(int i = 0; i < 26; i ++){
 4         if(p->next[i] != NULL){
 5             deleTrie(p->next[i]);
 6         }
 7     }
 8     free(p);
 9     return ;
10 }

 

查找：

1 int find(){
2     Nod* p = &t;
3     for(int i = 0; s[i]; i ++){
4         int a = s[i]-‘a‘;
5         if(p->next[a]==NULL) return 0;
6         p = p->next[a];
7     }
8     return p->num;
9 }

以 HDU1671 为例。

大意是求是否有某个数为另外一个树的前缀。

假设X1X2X3...Xn为Y1Y2Y3...Yn的前缀，那么有两种情况。

（一）：X在Y的后面，这时在插入X时，在Xn这里会有子节点。

（二）：X在Y的前面，这时在插入Y时，在Xn这里会被标记。

AC代码为：

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 char str[20];
 5 bool flag;
 6 struct Nod{
 7     bool is;
 8     Nod *next[26];
 9     Nod(){
10         is = false;
11         for(int i = 0; i < 26; i ++){
12             next[i] = NULL;
13         }
14     }
15 };
16 void mkTrie(Nod *root,char *s){
17     Nod*p = root;
18     for(int i = 0; s[i]; i ++){
19         int a = s[i] - ‘0‘;
20         if(p->next[a]==NULL)p->next[a] = new Nod;
21         if(p->is){
22             flag = true;
23         }
24         p = p->next[a];
25     }
26     p->is = true;
27     for(int i = 0; i < 26; i ++){
28         if(p->next[i]!=NULL){
29             flag = true;
30             break;
31         }
32     }
33 }
34 void deleTrie(Nod *p){
35     if(p == NULL) return;
36     for(int i = 0; i < 26; i ++){
37         if(p->next[i] != NULL){
38             deleTrie(p->next[i]);
39         }
40     }
41     free(p);
42     return ;
43 }
44 int main(){
45     int T,n;
46     scanf("%d",&T);
47     while(T--){
48         scanf("%d",&n);
49         Nod *t = new Nod;
50         flag = false;
51         for(int i = 0; i < n; i ++){
52             scanf("%s",str);
53             if(!flag){
54                 mkTrie(t,str);
55             }
56         }
57         if(flag)cout << "NO\n";
58         else cout << "YES\n";
59         deleTrie(t);
60     }
61     return 0;
62 }

 

　　

字典树


联系
我们