1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 struct Tire{
 7     bool isw;    //是否是一个单词
 8     Tire *next[26];
 9     Tire()
10     {
11         isw = false;
12         int i;
13         for(i=0;i<26;i++)
14             next[i] = NULL;
15     }
16 };
17 Tire root;
18 
19 void Insert(char word[])    //将word插入到字典树中，在最后标记这是一个单词
20 {
21     Tire *p = &root;
22     int i;
23     for(i=0;word[i];i++){
24         int t = word[i]-‘a‘;
25         if(p->next[t]==NULL)    //如果没有对应的节点
26             p->next[t] = new Tire;
27         p = p->next[t];
28     }
29     p->isw = true;    //标记到这为止是一个单词
30 }
31 
32 bool isWord(char str[])    //判断这个字符串是否为一个单词
33 {
34     Tire *p = &root;
35     int i;
36     for(i=0;str[i];i++){
37         int t = str[i]-‘a‘;
38         if(p->next[t]==NULL)    //如果没有对应的节点
39             return false;
40         p = p->next[t];
41     }
42     return p->isw;
43 }
44 char word[50010][101];    //字典
45 
46 int main()
47 {
48     int size=1,i,j;    //字典大小
49 
50     while(scanf("%s",word[size])!=EOF){    //读入字典
51         //if(word[size][0]==‘0‘) break;
52         Insert(word[size++]);
53     }
54     size--;
55 
56     //检查每一个单词，判断这个单词是否为Hat‘s word
57     for(i=1;i<=size;i++){
58         for(j=1;j<strlen(word[i]);j++){
59             char t[101],*p=word[i];
60             strncpy(t,word[i],j);
61             t[j]=‘\0‘;
62             p+=j;
63             if(isWord(t) && isWord(p)){    //如果这两部分都是单词，说明是Hat‘s word
64                 printf("%s\n",word[i]);
65                 break;
66             }
67         }
68     }
69     return 0;
70 }