题目大意
给定一些单词，要求你把所有的帽子单词找出来，如果某个单词恰好由另外两个单词连接而成，那么它就是帽子单词
题解
先把所有单词插入到Trie树，然后判断每个单词是不是帽子单词，做法就是：对于第i个单词，假设为s[0..n],枚举中间节点j，在Trie树上查询s[0..j]和s[j+1,…n]两个单词是否存在，存在的话说明它就是帽子词…WA了几发，找到帽子单词的时候忘记break了。。。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 50005
char s[MAXN][30];
const int maxnode=MAXN*25+100;
const int sigma_size=26;
struct Trie
{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
Trie(){sz=1;val[0]=0;memset(ch[0],0,sizeof(ch[0]));}
int idx(char c){return c-'a';}
void insert(char *s,int v)
{
int u=0,n=strlen(s);
for(int i=0;i<n;i++)
{
int c=idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(sz));
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=v;
}
bool find_prefix(const char *s,int len)
{
int u=0;
for(int i=0;i<len;i++)
{
int c=idx(s[i]);
if(!ch[u][c])
return false;
u=ch[u][c];
}
if(val[u]) return true;
return false;
} };
Trie trie;
int main()
{
//freopen("sb.txt","r",stdin);
//freopen("hehe.txt","w",stdout);
int cnt=0;
while(scanf("%s",s[cnt])!=EOF)
trie.insert(s[cnt++],cnt);
for(int i=0;i<cnt;i++)
{
int size=strlen(s[i]);
for(int j=1;j<size-1;j++)
{
if(trie.find_prefix(s[i],j)&&trie.find_prefix(s[i]+j,size-j))
{
printf("%s\n",s[i]);
break;
}
}
}
return 0;
}