【HDOJ】1247 Hat’s Words

字典树。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define MAXN 50005
 6 #define MAXL 25
 7 
 8 typedef struct Trie {
 9     bool f;
10     Trie *next[26];
11     Trie() {
12         f = false;
13         for (int i=0; i<26; ++i)
14             next[i] = NULL;
15     }
16 } Trie;
17 
18 Trie root;
19 char map[MAXN][MAXL], buf[MAXL];
20 int nn = 0;
21 
22 void create(char str[]) {
23     int i = 0, id;
24     Trie *p = &root, *q;
25 
26     while (str[i]) {
27         id = str[i] - 'a';
28         ++i;
29         if (p->next[id] == NULL) {
30             q = new Trie();
31             p->next[id] = q;
32         }
33         p = p->next[id];
34     }
35     p->f = true;
36 }
37 
38 bool find(char str[], int x) {
39     int i = 0, id;
40     Trie *p = &root;
41     bool f;
42 
43     while (i<x && str[i]) {
44         id = str[i] - 'a';
45         ++i;
46         if (p->next[id] == NULL)
47             return false;
48         p = p->next[id];
49     }
50     f = p->f;
51     if (!f) return false;
52 
53     p = &root;
54     while (str[i]) {
55         id = str[i] - 'a';
56         ++i;
57         if (p->next[id] == NULL)
58             return false;
59         p = p->next[id];
60     }
61     return p->f;
62 }
63 
64 int main() {
65     int i, j, len, n = 0;
66     bool f;
67 
68     while (scanf("%s", map[n]) != EOF)
69         create(map[n++]);
70 
71     for (i=0; i<n; ++i) {
72         len = strlen(map[i]);
73         f = false;
74         for (j=1; !f&&j<len-1; ++j)
75             f = find(map[i], j);
76         if (f)
77             printf("%s
", map[i]);
78     }
79 
80     return 0;
81 }