pku2001 Shortest Prefixes

http://poj.org/problem?id=2001
数据结构，Trie
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int CHARSET = 26, BASE = 'a', MAX_NODE = 20100;
 5 
 6 struct trie
 7 {
 8     int tot, root, child[MAX_NODE][CHARSET];
 9     bool flag[MAX_NODE];
10     int cnt[MAX_NODE];
11     trie()
12     {
13         memset(child[1], 0, sizeof(child[1]));
14         memset(cnt, 0, sizeof(cnt));
15         flag[1] = false;
16         root = tot = 1;
17     }
18     void insert(const char *str)
19     {
20         int *cur = &root;
21         for(const char *p=str; *p; ++p)
22         {
23             cur = &child[*cur][*p-BASE];
24             if(*cur == 0)
25             {
26                 *cur = ++tot;
27                 memset(child[tot], 0, sizeof(child[tot]));
28                 flag[tot] = false;
29             }
30             cnt[*cur] ++;
31         }
32         flag[*cur] = true;
33     }
34     int query(const char *str)
35     {
36         int cur = root;
37         int i = 1;
38         int j;
39         for(j=0; str[j]; j++, i++)
40         {
41             cur = child[cur][str[j]-BASE];
42             if(cnt[cur] == 1)
43             {
44                 return i;
45             }
46             if(str[j+1] == 0)
47             {
48                 return i;
49             }
50         }
51         return i;
52     }
53 };
54 char s[1002][22]; 
55 int main()
56 {
57     int i, j, n, m;
58     memset(s, 0, sizeof(s));
59     trie t;
60     for(i=1; ~scanf("%s", s[i]); i++)
61     {
62         t.insert(s[i]);
63     }
64     n = i-1;
65     for(i=1; i<=n; i++)
66     {
67         m = t.query(s[i]);
68         printf("%s ", s[i]);
69         for(j=0; j<m; j++)
70         {
71             printf("%c", s[i][j]);
72         }
73         printf("\n");
74     }
75     return 0;
76 }