Hat’s Words

 

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

题意：

寻找出单次表中一个单词是由另外两个单词组成的。

 

AC代码： 

 

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAXN 26

char str[50017][117];
struct node{
    bool isEnd;//用于判断是否为一个单词的结尾 
	node *next[MAXN]; //next是表示每层有多少种类的数
}Trie,*root;


void Init(node *root){//每个结点的初始化 
	root->isEnd = false; 
	for(int i=0;i<MAXN;i++)
		root->next[i]=NULL;
}

void insert(char *str){//建树 
    int len = strlen(str);
    node *p = root, *q;
    for(int i = 0; i < len; i++){
        int id = str[i]-'a';
        if(p->next[id] == NULL){//如果该子节点还未创建 
            q = (node *)malloc(sizeof(node));//动态分配空间 
            Init(q);//初始化 
	        p->next[id] = q; //节点连接 
        }
		p = p->next[id];//指针移动到下一个节点 
    }
    p->isEnd = true;//若为结尾，则将v改成-1表示
}
 
bool find(char *str){
    int len = strlen(str);
    node *p = root;
    for(int i = 0; i < len; i++){
        int id = str[i]-'a';
        p = p->next[id];
        if(p == NULL) //若为空集，表示不存以此为前缀的串
            return false;
    }
    if(p->isEnd == true)//说明是完全匹配
        return true;
    else
        return false;
}

void Freedom(node* p){//释放内存 
    for(int i = 0; i < MAXN; i++){
        if(p->next[i]!=NULL)
            Freedom(p->next[i]);
    }
    delete p;
}

int main(){
    root = (node *)malloc(sizeof(node));
   	Init(root);
    int cont = 0;//输入单词计数 
    while(scanf("%s",str[cont])!=EOF){
        insert(str[cont]);
        cont++;
    }
    char a[117], b[117];
    for(int i = 0; i < cont; i++){//每个单词进行遍历 
        int len = strlen(str[i]);
        for(int j = 1; j < len; j++){//切割点进行遍历 
        	//初始化a，b数组 
            memset(a,'\0',sizeof(a));
            memset(b,'\0',sizeof(b));
            //将一个单词str分割成两个单词放入a和b中 
            strncpy(a,str[i],j);//str数组的前一部分 
            strncpy(b,str[i]+j,len-j);//str数组的后一部分 
            if(find(a)==true && find(b)==true){//两部分都可以找到对应，则满足条件 
                printf("%s\n",str[i]);
                break;
            }
        }
    }
    Freedom(root);//动态字典树，有时会超内存,故需要记得释放内存 
    return 0;
}