首页 > 代码库 > Trie树
Trie树
Trie树,即字典树或单词查找树,主要用于大量字符串的检索、去重、排序等操作。
主要原理就是利用字符串的公共前缀建立一棵多叉树,牺牲空间换取时间。
1 //Trie树 2 #include <iostream> 3 #include <string> 4 using std::cin; 5 using std::cout; 6 using std::endl; 7 using std::string; 8 9 const int SIZE = 26; 10 const char BASE = ‘a‘; 11 12 class TrieNode { 13 public: 14 //is_terminal means that this char is the last one of this string 15 //we can get this string by going from the root to this terminal 16 bool is_terminal; 17 TrieNode **childs; 18 TrieNode() { 19 is_terminal = false; 20 childs = new TrieNode*[SIZE]; 21 for (int i = 0; i < SIZE; ++i) { 22 childs[i] = nullptr; 23 } 24 } 25 ~TrieNode() { 26 for (int i = 0; i < SIZE; ++i) { 27 delete childs[i]; 28 } 29 delete[] childs; 30 } 31 }; 32 33 class StringPatterns { 34 private: 35 TrieNode *root; 36 public: 37 StringPatterns() { 38 root = new TrieNode(); 39 } 40 ~StringPatterns() { 41 delete root; 42 } 43 void add_pattern(const string &pattern) { 44 TrieNode *now=root; 45 for(int i=0;i<pattern.length();i++){ 46 //this char is new in current level, means that this char is from a new different string 47 if(now->childs[pattern[i]-BASE]==nullptr){ 48 //add this char 49 now->childs[pattern[i]-BASE]=new TrieNode(); 50 } 51 //go to next char 52 now=now->childs[pattern[i]-BASE]; 53 } 54 //now points to the last char of this added string 55 now->is_terminal=true; 56 } 57 bool match(const string &buffer) const { 58 TrieNode *now=root; 59 for(int i=0;i<buffer.length();i++){ 60 if(now->childs[buffer[i]-BASE]==nullptr){ 61 return false; 62 } 63 now=now->childs[buffer[i]-BASE]; 64 } 65 return now->is_terminal; 66 } 67 }; 68 69 int main() { 70 StringPatterns trie; 71 int n; 72 cin >> n; 73 for (int i = 0; i < n; ++i) { 74 string pattern; 75 cin >> pattern; 76 trie.add_pattern(pattern); 77 } 78 string str_buffer; 79 cin >> str_buffer; 80 if (trie.match(str_buffer)) { 81 cout << "match success" << endl; 82 } else { 83 cout << "match failed" << endl; 84 } 85 return 0; 86 }
用Trie树求一个string的所有不相同的子串:
1 //find all different substrings of a string 2 #include <iostream> 3 #include <string> 4 using std::cin; 5 using std::cout; 6 using std::endl; 7 using std::string; 8 9 const int SIZE = 26; 10 const char BASE = ‘a‘; 11 12 class TrieNode { 13 public: 14 bool is_terminal; 15 TrieNode **childs; 16 TrieNode() { 17 is_terminal=false; 18 childs=new TrieNode*[SIZE]; 19 for(int i=0;i<SIZE;i++){ 20 childs[i]=nullptr; 21 } 22 } 23 ~TrieNode() { 24 for(int i=0;i<SIZE;i++){ 25 delete childs[i]; 26 } 27 delete[] childs; 28 } 29 }; 30 31 class StringPatterns { 32 private: 33 TrieNode *root; 34 //number of substrings 35 int subs; 36 public: 37 StringPatterns() { 38 subs=0; 39 root=new TrieNode(); 40 } 41 ~StringPatterns() { 42 delete root; 43 } 44 void add_pattern(const string &pattern) { 45 TrieNode *now=root; 46 for(int i=0;i<pattern.length();i++){ 47 now=root; 48 //add in all substrings starting with pattern[j] 49 for(int j=i;j<pattern.length();j++){ 50 if(now->childs[pattern[j]-BASE]==nullptr){ 51 //means this is a new different substring 52 now->childs[pattern[j]-BASE]=new TrieNode(); 53 subs++; 54 } 55 now=now->childs[pattern[j]-BASE]; 56 } 57 } 58 cout<<subs<<endl; 59 } 60 61 62 }; 63 64 int main() { 65 StringPatterns strp; 66 string it; 67 cin>>it; 68 strp.add_pattern(it); 69 return 0; 70 }
Trie树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。