題目鏈接:http://poj.org/problem?id=2001
另一種字典樹的寫法……


1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 struct trie{
6 int num;
7 int next[30];
8 int init(){
9 num = 1;
10 memset(next, -1, sizeof(next));
11 return 0;
12 }
13 }tree[100100];
14 int sz = 1;
15 const int rt = 0;
16 int idx(char c){
17 return c - 'a';
18 }
19 void insert(string s){
20 int p = rt, n = s.size();
21 for (int i = 0; i < n; i++){
22 int v = idx(s[i]);
23 if (tree[p].next[v] == -1){
24 tree[p].next[v] = sz;
25 tree[sz].init();
26 sz += 1;
27 }
28 else tree[tree[p].next[v]].num += 1;
29 p = tree[p].next[v];
30 }
31 }
32 void print(string s){
33 int p = rt, n = s.size();
34 for (int i = 0; i < n; i++){
35 int v = idx(s[i]);
36 putchar(s[i]);
37 if (tree[tree[p].next[v]].num == 1) return;
38 p = tree[p].next[v];
39 }
40 }
41 void init(){
42 sz = 1;
43 tree[0].init();
44 }
45 string s[2010];
46 int main(){
47 init();
48 int n = 0;
49 while(cin >> s[n]) insert(s[n++]);
50 for (int i = 0; i < n; i++){
51 cout << s[i] << " ";
52 print(s[i]);
53 printf("\n");
54 }
55 return 0;
56 }
57

