poj 2011 Shortest Prefixes 简单字典树

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #define INF 1e11
12 #define MAXN 10010 
13 using namespace std;
14 
15 
16 //适用于正负整数
17 template <class T>
18 inline bool scan_d(T &ret) {
19     char c; int sgn;
20     if (c = getchar(), c == EOF) return 0; //EOF
21     while (c != '-' && (c<'0' || c>'9')) c = getchar();
22     sgn = (c == '-') ? -1 : 1;
23     ret = (c == '-') ? 0 : (c - '0');
24     while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
25     ret *= sgn;
26     return 1;
27 }
28 
29 struct node{
30     int next[26];
31     int cnt;
32     void init()
33     {
34         cnt = 0;
35         memset(next,-1,sizeof(next));
36     }
37 }T[MAXN];
38 
39 int le;
40 
41 void Insert(string s)
42 {
43     int i = 0, p = 0;
44     while (s[i]) {
45         int x = s[i] - 'a';
46         if (T[p].next[x] == -1) {
47             T[le].init();
48             T[p].next[x] = le++;
49         }
50         p = T[p].next[x];
51         T[p].cnt++;
52         i++;
53     }
54 }
55 
56 void query(string s)
57 {
58     int i = 0, p = 0;
59     while (s[i])
60     {
61         int x = s[i] - 'a';
62         if (T[p].cnt == 1) break;
63             cout << s[i];
64         p = T[p].next[x];
65         i++;
66     }
67     //printf("%d
", T[p].cnt);
68 }
69 
70 string s[MAXN];
71 
72 int main()
73 {
74     le = 1;
75     T[0].init();
76     int n = 0;
77     while (cin >> s[n])
78     {
79         Insert(s[n++]);
80     }
81     //T[0].cnt = n;
82     for (int j = 0; j < n; ++j) {
83         cout << s[j] << " ";
84         query(s[j]);
85         cout << endl;
86     }
87     //system("pause");
88     return 0;
89 }