Hat’s Words

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4846    Accepted Submission(s): 1851

a
ahat
hat
hatword
hziee
word

ahat
hatword

题目大意：给你一些单词，输出其中是这些单词里面由其他两个单词拼接成的那些单词。

解题思路：刚开始就想，用字典树将所有的单词保存起来，在每个单词的结尾处标记是单词结尾，然后查找每个单词，每次查到该单词的某个字母时，如果该字母时某个单词的结尾，则计数器加1，然后将查找指针指向root，接着查找剩下的部分，到查找结束时，如果计数器返回2，则，该单词符合要求。

咋一看，思路是对的，并且比较容易实现，但是仔细想想，如果一个单词既是两个单词拼接的结果，又是三个、四个单词拼接的结果时，那么这个单词应该是符合题意的，但是用刚才的那种方法查找到的却是3、4，因为我们无法知道从哪里分割才是有可能符合题意的。看下面的数据：

a
ha
t
aha
hat
ahat

aha
hat
ahat

如果用刚才的思路，则不会输出ahat。

那么我们只能采用暴力了，对每一个单词分割超找即可，虽然有点浪费时间，但是可以过！

代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 26
char s[50010][100];
struct node {
    struct node *child[N];
	int flag;
};

struct node *root;
void inital(struct node *p) {
    int i;
    for(i=0;i<N;i++) {
        p->child[i]=NULL;
    }
	p->flag=0;
    return;
}

void insert(char *str) {
    int i,len,k;
    struct node *newnode,*current;
    len=strlen(str);
    current=root;
    if(len==0) return ;
    
    for(i=0;i<len;i++) {
        k=str[i]-'a';
        if(current->child[k]!=NULL)
            current=current->child[k];
        else {
            newnode=(struct node *)malloc(sizeof(struct node));
            inital(newnode);
            current->child[k]=newnode;
            current=newnode;
        }
    }
	current->flag=1;
}

int find(char *str) {
    int len,i,k;
    struct node *current;
    current=root;
    len=strlen(str);
    for(i=0;i<len;i++) {
        k=str[i]-'a';
        if(current->child[k]!=NULL) {
            current=current->child[k];
        }
        else 
            return 0;
    }
    return current->flag;
}

int main() {
    
    int i,j,ans,n=0,len;
    char s1[100],s2[100];
    root=(struct node *)malloc(sizeof(struct node));
    inital(root);
    while(scanf("%s",s[n])!=EOF) {
    //while(scanf("%s",s[n]),s[n][0]!='#') {
        insert(s[n]);
        n++;
    }
    for(i=0;i<n;i++) {
        len=strlen(s[i]);
        for(j=1;j<=len-1;j++) {
            strncpy(s1,s[i],j);
            s1[j]='\0';
            strncpy(s2,s[i]+j,len-j);
            s2[len-j]='\0';
            ans=find(s1)+find(s2);
            if(ans==2){
                printf("%s\n",s[i]);
                break;
            }
        }
    }
    return 0;    
}

/*
a
ha
t
aha
hat
ahat


aha
hat
ahat

*/