# hdu 1247 Hat’s Words

                       **Hat’s Words**

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



Intput
a
aa
aaa
hat
word
s
hatwords

Output
aa
aaa

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
const int maxn = 26;
struct Trie//结点声明
{
struct Trie *next[maxn];//孩子分支
bool isStr;//标记是否构成单词
};

void Insert(Trie *root,const char *s)//将单词s插入Trie树
{
if(root==NULL || *s=='\0')
return;
//int i;
Trie *p = root;
while(*s != '\0')
{
if(p->next[*s-'a'] == NULL) //如果不存在，则建立结点
{
Trie *tmp = (Trie*)malloc(sizeof(Trie));
for(int i=0; i<maxn; i++)
tmp->next[i] = NULL;
tmp->isStr = false;
p->next[*s-'a'] = tmp;
p = p->next[*s-'a'];
}
else
p = p->next[*s-'a'];
s++;
}
p->isStr = true;//单词结束的地方标记此处可以构成一个单词
}

int Find(Trie *root, const char *s)
{
Trie *p = root;
while(p!=NULL && *s!='\0')
{
p = p->next[*s-'a'];
s++;
}
return (p!=NULL && p->isStr==true);//在单词结束处的标记为true时，单词才存在
}

void Del(Trie *root)//释放整个Trie树的空间
{
for(int i=0; i<maxn; i++)
{
if(root->next[i] != NULL)
Del(root->next[i]);
}
free(root);
}
char s[50000][100];
char str[100];
int main()
{
int m,n; //n为建立Trie树输入的单词数，m为要查找的单词数
Trie *root = (Trie *)malloc(sizeof(Trie));
for(int i=0; i<maxn; i++)
root->next[i] = NULL;
root->isStr = false;
int cnt = 0;
while(scanf("%s",str) != EOF)
{
strcpy(s[cnt++],str);
Insert(root, str);
}
for(int i=0; i<cnt; i++)
{
for(int j=1; j<strlen(s[i]); j++)
{
char tmp1[100] = {'\0'};
char tmp2[100] = {'\0'};
/*strncpy函数是指(char s1,char s2, int len)三个参数，将s2的len个数
复制给s1,但是最后要加'\0'要不然就会。。。。*/
strncpy(tmp1, s[i], j);
strncpy(tmp2, s[i]+j, strlen(s[i])-j);
if(Find(root, tmp1) && Find(root, tmp2))
{
printf("%s\n",s[i]);
break;
}
}
}
Del(root);
return 0;
}


+ 订阅