首页 > 代码库 > ·专题」 Trie（前缀树）

·专题」 Trie（前缀树）

2024-07-04 16:35:31   235人阅读

重新整理Trie的内容，还有一种叫做双链键树，不过到现在也不会写。

 

Trie 可以称为字典树，也叫做前缀树，叫字典树很形象，叫前缀树可以很好的区分，因为还有一种树叫做后缀树

自己就不瞎总结了，写估计也写不好。关键是时间不允许。

参考两个blog A   B

 

先给一个比较标准的模板

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 #define MAXBRANCH 26
 8 #define CLR(a,b) memset(a,b,sizeof(a))
 9 
10 typedef struct _TRIENODE_
11 {
12     bool isStr;
13     _TRIENODE_* pNext[MAXBRANCH];
14 
15 }TrieNode,*PTrieNode;
16 
17 PTrieNode CreateNode()
18 {
19     PTrieNode Node = (PTrieNode)malloc(sizeof(TrieNode));
20     for(int i=0;i<MAXBRANCH;i++)
21         Node->pNext[i] = NULL;
22     Node->isStr = false;
23     return Node;
24 }
25 
26 void Insert(PTrieNode Root,char* words)
27 {
28     PTrieNode Location = Root;
29     while(*words)
30     {
31         if(Location->pNext[*words - ‘a‘] == NULL)
32         {
33             Location->pNext[*words - ‘a‘] = CreateNode();
34         }
35 
36         Location = Location->pNext[*words - ‘a‘];
37 
38         words++;
39     }
40 
41     Location->isStr = true;
42 }
43 
44 
45 bool Search(PTrieNode Root,char* words)
46 {
47     PTrieNode Location = Root;
48     while(*words != ‘\0‘ && Location->pNext[*words - ‘a‘] != NULL)
49     {
50         Location = Location->pNext[*words - ‘a‘];
51         words++;
52     }
53 
54     return (Location!=NULL && Location->isStr == true);
55 }
56 
57 void Delete(PTrieNode Root)
58 {
59     for(int i=0;i<MAXBRANCH;i++)
60     {
61         if(Root->pNext[i] != NULL)
62         {
63             Delete(Root->pNext[i]);
64         }
65     }
66 
67     free(Root);
68 }
69 
70 
71 int main()
72 {
73 
74     char test[4][100] = {"iloveyou","mylove","dont","oh"};
75     char* str = (char*)malloc(sizeof(char)*100);
76     PTrieNode Root = CreateNode();
77 
78     for(int i=0;i<4;i++)
79     {
80         printf("%s\n",test[i]);
81         Insert(Root,test[i]);
82     }
83 
84     printf("Input string to search:");
85     gets(str);
86     if(Search(Root,str))
87         printf("Finded!");
88     else
89         printf("Failed!");
90 
91     return 0;
92 }
View Code

然后给一个比较简洁的可以比赛用的模板 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<malloc.h>
 4 using namespace std;
 5 #define CLR(a,b) memset(a,b,sizeof(a))
 6 
 7 struct Trie
 8 {
 9     struct Node
10     {
11         Node* next[26];
12         int cnt;
13     };
14 
15     Node* root;
16 
17     void Init()
18     {
19         root = CreateNode();
20     }
21 
22     Node* CreateNode()
23     {
24         Node* tmp = (Node*)malloc(sizeof(Node));
25         for(int i=0;i<26;i++)
26             tmp->next[i] = NULL;
27         tmp->cnt = 0;
28         return tmp;
29     }
30 
31     void Insert(char* str)
32     {
33         Node* p = root;
34         while(*str)
35         {
36             int t = *str - ‘a‘;
37             if(p->next[t] == NULL)
38                 p->next[t] = CreateNode();
39             p = p->next[t];
40             str++;
41         }
42         p->cnt++;
43     }
44 
45     bool Search(char* str)
46     {
47         Node* p = root;
48         while(*str && p)    //这里要小心，别写错 
49         {
50             p = p->next[*str - ‘a‘];
51             str++;
52         }
53         if(p && p->cnt)
54             return true; 
55         else
56             return false;
57     }
58 
59     void Delete(Node* rt)
60     {
61         if(rt == NULL)
62             return;
63         for(int i=0;i<26;i++)
64         {
65             if(rt->next[i])
66             {
67                 Delete(rt->next[i]);
68             }
69         }
70         free(rt);
71     }
72 }Trie;
73 
74 
75 int main()
76 {
77 
78     char test[4][100] = {"iloveyou","mylove","dont","oh"};
79     char* str = (char*)malloc(sizeof(char)*100);
80     
81     Trie.Init();
82     for(int i=0;i<4;i++)
83     {
84         printf("%s\n",test[i]);
85         Trie.Insert(test[i]);
86     }
87 
88     printf("Input string to search:");
89     gets(str);
90     if(Trie.Search(str))
91         printf("YES!");
92     else
93         printf("NO!");
94 
95     return 0;
96 }
View Code

 

 

然后是三道水题，先来这三道，其他的以后补充

HDU 1075 what are you tlaking about?
/*
简要说明题意：题目意思很清楚，就是外星人给了你一本日记和一本字典，你需要把日记通过字典来翻译。
分析：需要增加一个域来存放单词的明文，翻译的时候找到单词的密文，需要对应输出单词的明文，还要注意其他ascii字符的输出，然后就是裸的Trie了
*/
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 #define CLR(a,b) memset(a,b,sizeof(a))
  8 #define MAXBRANCH 26
  9 
 10 char str[20];
 11 char s1[20],s2[20],s3[3003];
 12 
 13 typedef struct _TRIENODE_
 14 {
 15     bool isStr;
 16     _TRIENODE_* pNext[MAXBRANCH];
 17     char Dir[15];
 18 }TrieNode,*PTrieNode;
 19 
 20 PTrieNode CreateNode()
 21 {
 22     PTrieNode Node = (PTrieNode)malloc(sizeof(TrieNode));
 23     for(int i=0;i<MAXBRANCH;i++)
 24     {
 25         Node->pNext[i] = NULL;
 26     }
 27     
 28     Node->isStr = false;
 29     CLR(Node->Dir,0);
 30     return Node;
 31 }
 32 
 33 void Insert(PTrieNode Root,char* words)
 34 {
 35     PTrieNode Location = Root;
 36     while(*words)
 37     {
 38         if(Location->pNext[*words - ‘a‘] == NULL)
 39         {
 40             Location->pNext[*words - ‘a‘] = CreateNode();
 41         }
 42         Location = Location->pNext[*words - ‘a‘];
 43         words++;
 44     }
 45     Location->isStr = true;
 46     strcpy(Location->Dir,s1);
 47 }
 48 
 49 bool Search(PTrieNode Root,char* words)
 50 {
 51     PTrieNode Location = Root;
 52     while(*words)
 53     {
 54         if(Location->pNext[*words - ‘a‘] == NULL)
 55             return false;
 56         Location = Location->pNext[*words - ‘a‘];
 57         words++;
 58     }
 59     if(Location->isStr)
 60     {
 61         printf("%s",Location->Dir);
 62         return true;
 63     }
 64 }
 65 void Delete(PTrieNode Root)
 66 {
 67     for(int i=0;i<MAXBRANCH;i++)
 68     {
 69         if(Root->pNext[i]  != NULL)
 70         {
 71             Delete(Root->pNext[i]);
 72         }
 73     }
 74     
 75     free(Root);
 76 }
 77 
 78 int main()
 79 {
 80     scanf("%s",str);
 81     PTrieNode Root = CreateNode();
 82     while(scanf("%s %s",s1,s2) && strcmp("END",s1)!=0)
 83     {
 84         Insert(Root,s2);
 85         CLR(s1,0);CLR(s2,0);
 86     }    
 87     getchar();
 88     while(gets(s3) && strcmp(s3,"END")!=0)
 89     {
 90         char* se = s3;
 91         char* st = s3;
 92         while(*st)
 93         {
 94             CLR(str,0);
 95             int len = 0;
 96             while(*st>=‘a‘ && *st <= ‘z‘)    st++,len++;
 97             if(len)    
 98             {
 99                 strncpy(str,se,len);
100                 if(!Search(Root,str))
101                     printf("%s",str);
102             }
103             else
104             {
105                 printf("%c",*st);
106                 st++;
107             }
108             se = st;
109         }
110         CLR(s3,0);
111         printf("\n");
112     }
113     return 0;
114 }
View Code
HDU 1247 Hat‘s words
/*
题意：先读入所有单词，并插入字典，然后问，哪些单词是hat‘s words（由两个已经在字典里的单词组成）
分析：对每一个单词进行拆分，拆分成两部分，并在字典中查找，如果均查找到，则为所求
*/
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<malloc.h>
 4 using namespace std;
 5 #define CLR(a,b) memset(a,b,sizeof(a))
 6 
 7 struct Trie
 8 {
 9     struct Node
10     {
11         Node* next[26];
12         int cnt;
13     };
14 
15     Node* root;
16 
17     void Init()
18     {
19         root = CreateNode();
20     }
21 
22     Node* CreateNode()
23     {
24         Node* tmp = (Node*)malloc(sizeof(Node));
25         for(int i=0;i<26;i++)
26             tmp->next[i] = NULL;
27         tmp->cnt = 0;
28         return tmp;
29     }
30 
31     void Insert(char* str)
32     {
33         Node* p = root;
34         while(*str)
35         {
36             int t = *str - ‘a‘;
37             if(p->next[t] == NULL)
38                 p->next[t] = CreateNode();
39             p = p->next[t];
40             str++;
41         }
42         p->cnt++;
43     }
44 
45     int Search(char* str)
46     {
47         Node* p = root;
48         while(*str && p)
49         {
50             p = p->next[*str - ‘a‘];
51             str++;
52         }
53         return (p && p->cnt);
54     }
55 
56     void Delete(Node* rt)
57     {
58         if(rt == NULL)
59             return;
60         for(int i=0;i<26;i++)
61         {
62             if(rt->next[i])
63             {
64                 Delete(rt->next[i]);
65             }
66         }
67         free(rt);
68     }
69 }Trie;
70 
71 char words[50005][110];
72 
73 int main()
74 {
75     int i = 0, j = 0, n = 0;    
76     Trie.Init();
77     while(gets(words[n]))
78     {
79         Trie.Insert(words[n++]);
80     }
81     for(i=0;i<n;i++)
82     {
83         int len = strlen(words[i]);
84         for(j=1;j<len;j++)
85         {
86             char t1[110],t2[110];
87             CLR(t1,0);CLR(t2,0);
88             strncpy(t1,words[i],j);
89             strncpy(t2,words[i]+j,len-j);
90             if(Trie.Search(t1) && Trie.Search(t2))
91             {
92                 printf("%s\n",words[i]);
93                 break;
94             }
95         }
96     }
97     return 0;
98 }
View Code
HDU 1251 统计难题
/*
几乎是裸的Trie，稍加改动统计方式即可
*/
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<malloc.h>
 4 using namespace std;
 5 #define CLR(a,b) memset(a,b,sizeof(a))
 6 
 7 struct Trie
 8 {
 9     struct Node
10     {
11         Node* next[26];
12         int cnt;
13     };
14 
15     Node* root;
16 
17     void Init()
18     {
19         root = CreateNode();
20     }
21 
22     Node* CreateNode()
23     {
24         Node* tmp = (Node*)malloc(sizeof(Node));
25         for(int i=0;i<26;i++)
26             tmp->next[i] = NULL;
27         tmp->cnt = 0;
28         return tmp;
29     }
30 
31     void Insert(char* str)
32     {
33         Node* p = root;
34         while(*str)
35         {
36             int t = *str - ‘a‘;
37             if(p->next[t] == NULL)
38                 p->next[t] = CreateNode();
39             p = p->next[t];
40             p->cnt++;
41             str++;
42         }
43 //        p->cnt++;
44     }
45 
46     int Search(char* str)
47     {
48         Node* p = root;
49         while(*str && p)
50         {
51             p = p->next[*str - ‘a‘];
52             str++;
53         }
54         if(p && p->cnt)
55             return p->cnt;
56         else
57             return 0;
58     }
59 
60     void Delete(Node* rt)
61     {
62         if(rt == NULL)
63             return;
64         for(int i=0;i<26;i++)
65         {
66             if(rt->next[i])
67             {
68                 Delete(rt->next[i]);
69             }
70         }
71         free(rt);
72     }
73 }Trie;
74 
75 
76 char temp[1000000];
77 
78 int main()
79 {
80     Trie.Init();
81     while(gets(temp),*temp)
82     {
83         Trie.Insert(temp);    
84     }    
85     while(~scanf("%s",temp))
86     {
87         printf("%d\n",Trie.Search(temp));
88     }
89     return 0;
90 }
View Code
 
































        

            
                
                  
                
                

                    联系

                    我们