题意：
给你若干个单词（不超过50000个），构成一个字典，输出这个字典中所有的帽子单词（Hat's word）。
帽子单词（Hat's word）：由两个已在字典中出现的单词构成。
思路：
根据输入的单词构建字典树，在插入的最后做一个这是“单词”的标记。我是用一个bool型来标记，默认为false，不是单词；如果为true，则说明到这个位置为止是一个单词。将所有单词记录下来，然后每一个单词将它拆分成两份，分别判断这两份是否为一个“单词”（在字典中出现过的字符串），这样每一个单词需要判断len-1次。例如，ahat，需要判断a和hat，ah和at，aha和t。第一组符合两份都是单词，所以这是一个帽子单词，输出该单词。
注意：
如果已经判断出这个单词是一个帽子单词，别忘了break退出循环，否则可能会重复输出。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
struct Tire
{
bool isw; //是否是一个单词
Tire *next[26];
Tire()
{
isw=false;
memset(next,0,sizeof(next));
}
}root;
string s[50005];
int n=0;
void insert(const string &s) //将word插入到字典树中，在最后标记这是一个单词
{
Tire *p=&root;
int index;
for(int i=0;s[i];i++)
{
index=s[i]-'a';
if(!p->next[index])
p->next[index]=new Tire;
p=p->next[index];
}
p->isw=true; //标记到这为止是一个单词
}
bool find(const string &s) //判断这个字符串是否为一个单词
{
Tire *p=&root;
int index;
for(int i=0;s[i];i++)
{
index=s[i]-'a';
if(!p->next[index])
return false;
p=p->next[index];
}
return p->isw;
}
int main()
{
// freopen("E:\\ACM\\test.txt","r",stdin);
while(cin>>s[n])
{
insert(s[n++]);
}
for(int i=1;i<n;i++)
{
for(int j=1;j<s[i].size();j++)
{
string s1=s[i].substr(0,j); //分割单词成两部分
string s2=s[i].substr(j,s[i].size());
if(find(s1)&&find(s2))
{
cout<<s[i]<<endl;
break;
}
}
}
return 0;
}
