Hat’s Words

题意：给出一张单词表求有多少个单词是由单词表里的两个单词组成，可以重复！按字典序输出这些单词。

思路：先建一个字典树，然后枚举每个单词，把每个单词任意拆分两部分然后查找。

目测数据不强，开始不知道单词长度都不敢下手了。。

struct tree

{

    bool f;

    tree *next[N];

    tree()

    {

        for(int i=0;i<N;i++) next[i]=NULL;

        f=false;

    }

};

void insert(tree *root,char *s)

{

    tree *p=root;

    while(*s!='\0')

    {

        if(p->next[*s-'a']==NULL)

        {

            tree *temp=new tree();

            p->next[*s-'a']=temp;

        }

        p=p->next[*s-'a'];

        s++;

    }

    p->f=true;

}

int find(tree *root,char *s)

{

    tree *p=root;

    while(p!=NULL&&*s!='\0')

    {

        p=p->next[*s-'a'];

        s++;

    }

    if(p==NULL) return false;

    return  p->f;

}

void del(tree *root)

{

    for(int i=0;i<N;i++)

        if(root->next[i]!=NULL)

        del(root->next[i]);

    delete(root);

}

char s[50001][100],s1[100],s2[100];

int main()

{

    tree *root=new tree();

    int num=0;

    while(~scanf("%s",s[num++]))

    {

        insert(root,s[num-1]);

    }

    for(int i=0;i<num;i++)

    {

        int len=strlen(s[i]);

        for(int j=0;j<len;j++)

        {

            int l1=0,l2=0;

            for(int k=0;k<j;k++) s1[l1++]=s[i][k];//分成两部分

            for(int k=j;k<len;k++) s2[l2++]=s[i][k];

            s1[l1]='\0',s2[l2]='\0';

            if(find(root,s1)&&find(root,s2))

            {

                puts(s[i]);

                break;

            }

        }

    }

    del(root);

    return 0;

}