首页 > 代码库 > ·专题」 Trie(前缀树)
·专题」 Trie(前缀树)
重新整理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 }
然后给一个比较简洁的可以比赛用的模板
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 }
然后是三道水题,先来这三道,其他的以后补充
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 }
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 }
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。