Trie模板——来源自Luolc2012

 1 /*==================================================*\
 2   [Trie] 字典树
 3   support:
 4         - insert O(L)
 5         - query O(L)
 6         - delete O(L)
 7   Trie[i]存储第i个节点的信息:
 8         next[j]: 下一个字符为j时 对应的节点编号
 9         fa: 父亲节点编号
10         cnt: 字符出现次数  
11 \*==================================================*/
12 
13 #include <cstdio>
14 #include <cstring>
15 #include <iostream>
16 #include <algorithm>
17 #include <queue>
18 #include <vector>
19 #include <map>
20 #include <set>
21 #include <string>
22 using namespace std;
23 //----------------------------------------------
24 #define CL(a,num) memset(a,num,sizeof(a));
25 #define BtoA(x,y) memcpy(x,y,sizeof(x));
26 #define eps  1e-12
27 #define inf  0x7fffffff
28 typedef    __int64    LL;
29 //----------------------------------------------
30 const int Node_max = 100000 + 5;
31 
32 struct Node {
33     int next[26];
34     // including a...z
35     int fa, cnt, flag;    
36 } Trie[Node_max];
37 // root = Trie[0]
38 int Trie_size;
39 #define t_s Trie_size
40 
41 int Trie_ins(char str[]) {
42     int len = strlen(str);
43     int tmp = 0;
44     for(int i = 0; i < len; ++i) {
45         if(!Trie[tmp].next[str[i] - 'a']) {
46             Trie[tmp].next[str[i] - 'a'] = ++t_s;    
47             Trie[t_s].fa = tmp;
48         }
49         tmp = Trie[tmp].next[str[i] - 'a'];
50     }
51     return ++Trie[tmp].cnt;
52     // let the appear_times of str increase then return it
53 }
54 int Trie_query(char str[]) {
55     //return the appear_times of str
56     int len = strlen(str);
57     int tmp = 0;
58     for(int i = 0; i < len; ++i) {
59         if(!Trie[tmp].next[str[i] - 'a'])
60             return -1;    // if can't find str
61         tmp = Trie[tmp].next[str[i] - 'a'];
62     }
63     return Trie[tmp].cnt;
64 }
65 int Trie_del(char str[]) {
66     int len = strlen(str);
67     int tmp = 0;
68     for(int i = 0; i < len; ++i) {
69         if(!Trie[tmp].next[str[i] - 'a'])
70             return -1; // if can't find str
71         tmp = Trie[tmp].next[str[i] - 'a'];    
72     }
73     return --Trie[tmp].cnt;
74     // let the appear_times of str decrease then return it
75 }
76 int main() {
77     char str[20];
78     while(true) {
79         int op;
80         cin >> op;
81         switch(op) {
82             case 0: //ins
83                 cin >> str;
84                 cout << Trie_ins(str) << endl;
85                 break;
86             case 1: //query
87                 cin >> str;
88                 cout << Trie_query(str) << endl;
89                 break;
90             case 2: //del
91                 cin >> str;
92                 cout << Trie_del(str) << endl;
93                 break;
94         }
95     }
96     return 0;    
97 }

--------------------------------------

欢迎您，进入我系程序猿的cnBlog博客。

你不能改变你的过去，但你可以让你的未来变得更美好。一旦时间浪费了，生命就浪费了。

You cannot improve your past, but you can improve your future. Once time is wasted, life is wasted.

--------------------------------------