Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6156 Accepted Submission(s): 2289
Problem Description
A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.
Output
Your output should contain all the hat’s words, one per line, in alphabetical order.
Sample Input
a
ahat
hat
hatword
hziee
word
Sample Output
ahat
hatword
分析：先把词典单词存入字典树，然后对每个单词进行枚举拆分，如m长度的单词要拆分m-1次，最后根据字典树判断是否拆分后的两部分单词能否都可以找到
程序：
#include"string.h"
#include"stdio.h"
#define M 50002
#include"stdlib.h"
struct st
{
int next[28];
int w;
}tree[M*5];
int index;
void creat(int k,char *ch)
{
int len=strlen(ch);
int i,s=0;
for(i=1;i<=len;i++)
{
int m=ch[i-1]-'a'+1;
if(tree[s].next[m]==0)
{
if(i==len)
tree[index].w=k;
tree[s].next[m]=index++;
}
else
{
if(i==len)
tree[tree[s].next[m]].w=k;
}
s=tree[s].next[m];
}
}
int finde(char *ch)
{
int len=strlen(ch);
int i,s=0;
for(i=1;i<=len;i++)
{
int m=ch[i-1]-'a'+1;
if(tree[s].next[m]!=0)
{
if(i==len&&tree[tree[s].next[m]].w!=0)
return 1;
s=tree[s].next[m];
}
else
return 0;
}
return 0;
}
char ch[M][33];
int main()
{
int k=1,i,j,t;
index=1;
memset(tree,0,sizeof(tree));
while(scanf("%s",ch[k])!=EOF)
{
creat(k,ch[k]);
k++;
}
char ch1[33],ch2[33];
int t1,t2;
for(i=1;i<k;i++)
{
int m=strlen(ch[i]);
for(j=1;j<m;j++)
{
t1=t2=0;
for(t=0;t<j;t++)
{
ch1[t1++]=ch[i][t];
}
ch1[t1]=' ';
for(t=j;t<m;t++)
{
ch2[t2++]=ch[i][t];
}
ch2[t2]=' ';
if(finde(ch1)&&finde(ch2))
{
puts(ch[i]);
break;
}
}
}
return 0;
}