Hat’s Words
题意：给出一张单词表求有多少个单词是由单词表里的两个单词组成，可以重复！按字典序输出这些单词。
思路：先建一个字典树，然后枚举每个单词，把每个单词任意拆分两部分然后查找。
目测数据不强，开始不知道单词长度都不敢下手了。。
struct tree
{
bool f;
tree *next[N];
tree()
{
for(int i=0;i<N;i++) next[i]=NULL;
f=false;
}
};
void insert(tree *root,char *s)
{
tree *p=root;
while(*s!='\0')
{
if(p->next[*s-'a']==NULL)
{
tree *temp=new tree();
p->next[*s-'a']=temp;
}
p=p->next[*s-'a'];
s++;
}
p->f=true;
}
int find(tree *root,char *s)
{
tree *p=root;
while(p!=NULL&&*s!='\0')
{
p=p->next[*s-'a'];
s++;
}
if(p==NULL) return false;
return p->f;
}
void del(tree *root)
{
for(int i=0;i<N;i++)
if(root->next[i]!=NULL)
del(root->next[i]);
delete(root);
}
char s[50001][100],s1[100],s2[100];
int main()
{
tree *root=new tree();
int num=0;
while(~scanf("%s",s[num++]))
{
insert(root,s[num-1]);
}
for(int i=0;i<num;i++)
{
int len=strlen(s[i]);
for(int j=0;j<len;j++)
{
int l1=0,l2=0;
for(int k=0;k<j;k++) s1[l1++]=s[i][k];//分成两部分
for(int k=j;k<len;k++) s2[l2++]=s[i][k];
s1[l1]='\0',s2[l2]='\0';
if(find(root,s1)&&find(root,s2))
{
puts(s[i]);
break;
}
}
}
del(root);
return 0;
}