## HDU 1247 解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=1247

## Hat’s Words

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

### 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```

### CODE

```#include<stdio.h>   struct tree { bool t;//记录以该节点作为结尾是否有单词存在 tree *node[26]; tree(){ t=false; for(int i=0;i<26;++i) node[i]=NULL; } } *root;   void insert(char *s) { char c; tree *p=root; for(int i=0;s[i];++i){ c=s[i]-'a'; if(p->node[c]==NULL) p->node[c]=new tree(); p=p->node[c]; } p->t=true; }   bool find(char *s) { tree *p=root; char c; for(int i=0;s[i];++i){ c=s[i]-'a'; if(p->node[c]) p=p->node[c]; else return false; } return p->t; }   void release(tree *p) { for(int i=0;i<26;++i) if(p->node[i]) release(p->node[i]); delete(p); }   int main() { int i,j,k,t,cnt=0; char l[20],r[20]; char D[50000][20]; root=new tree(); while(gets(D[cnt++])) insert(D[cnt-1]);   for(i=0;i<cnt;i++){ for(j=1;D[i][j];++j){ for(k=0;k<j;++k) l[k]=D[i][k]; l[k]='';   for(t=0;D[i][k];++k) r[t++]=D[i][k]; r[t]='';   if(find(l)&&find(r)){ printf("%sn",D[i]); break; } } } release(root); return 0; }```
» 本博客采用署名 2.5 中国大陆许可协议进行许可，本文版权归作者所有，欢迎转载，但必须在明显位置给出原文连接。