hihocoder1014 Trie树

问题描述:

Trie树在字符串处理中的应用十分重要，最典型的应用就是输入法和搜索引擎中的字符串自动补全功能。其核心思想是用一颗树来存储一个字典，树的每一条边表示单词的一个字符，在每个节点上记录以从根节点到当前节点所经过的路径为前缀的字符串个数。

利用字典树，可以实现O(log(n))的单词插入、单词查询、查询以某个前缀开头的字符串数目等。

题目链接：http://hihocoder.com/problemset/problem/1014

我的代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 #define MAX_CH 26
 7 #define MAX_NODE 1000005
 8 
 9 int nodecnt;
10 
11 struct TrieNode
12 {
13     int cnt;
14     TrieNode *p[MAX_CH];
15     void init()
16     {
17         cnt = 0;
18         for(int i=0; i<MAX_CH; ++i) p[i] = NULL;
19     }
20     int query(char *s)
21     {
22         int idx = s[0]-'a';
23         if(p[idx]!=NULL)
24         {
25             if(s[1]=='') return p[idx]->cnt;
26             else return p[idx]->query(s+1);
27         }
28         else
29         {
30             return 0;
31         }
32     }
33 }t_node[MAX_NODE];
34 
35 struct Trie
36 {
37     TrieNode *rt;
38     void init()
39     {
40         rt = &t_node[0];
41         rt->init();
42         nodecnt = 1;
43     }
44     void insert(char *s)
45     {    
46         TrieNode *now = rt;    
47         for(int i=0; s[i]; ++i)
48         {
49             int idx = s[i]-'a';
50             if(now->p[idx]==NULL)
51             {
52                 now->p[idx] = &t_node[nodecnt++];
53                 now->p[idx]->init();
54             }
55             ++(now->p[idx]->cnt);
56             now = now->p[idx];
57         }
58     }
59     int query(char *s)
60     {
61         return rt->query(s);
62     }
63 }trie;
64 
65 int main()
66 {
67     int n, m;
68     char s[20];
69     while(scanf("%d", &n)!=EOF)
70     {
71         trie.init();
72             
73         while(n--)
74         {
75             scanf("%s", s);
76             trie.insert(s);
77         }
78         
79         scanf("%d", &m);
80         while(m--)
81         {
82             scanf("%s", s);
83             printf("%d
", trie.query(s));
84         }
85     }    
86     return 0;
87 }