HDU 1247-Hat’s Words(辞書ツリー)

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

 
 
あなたにいくつかの単语をあげて、出力の中でこれらの単语の中でその他の2つの単语からつなぎ合わせたあれらの単语です.
最初から、辞書の木ですべての単語を保存し、各単語の末尾に単語の末尾をマークし、各単語を検索し、その単語のアルファベットを調べるたびに、そのアルファベットの末尾に単語の末尾を付けると、カウンタに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
",s[i]);
                break;
            }
        }
    }
    return 0;    
}

/*
a
ha
t
aha
hat
ahat


aha
hat
ahat

*/