字典树

1 class Trie { 2     public: 3         Trie() { 4             root = new Node(); 5         } 6  7         ~Trie() { 8             destroy(root); 9         }10 11         void insert(string word) {12             Node* next = root;13             for (int i = 0; i < word.length(); ++i) {14                 if (next->next[word[i] - 'a'] == NULL) {15                     next->next[word[i] - 'a'] = new Node();16                 }17                 next = next->next[word[i] - 'a'];            18             }19             next->val++; // 只要最尾个字符的位置计数20         }21 22         int search(string word) {23             Node* next = root;24             int i = 0;25             for (; i < word.length() && next != NULL; ++i) {26                 next = next->next[word[i] - 'a'];27             }28             if (i == word.length() && next != NULL) {29                 return next->val;30             } else {31                 return 0;32             }    33         }34 35     private:36         struct Node {37             int val;38             Node *next[26];39             Node(): val(0) {40                 memset(next, 0, sizeof(Node*) * 26);41             }42         };43 44         void destroy(Node* p) {45             if (p == NULL) return;46             for (int i = 0; i < 26; ++i) {47                 destroy(p->next[i]);48             }49             delete p;50         }51         Node* root;    52 };