hdu1247 字典树

开始以为枚举会超时，因为有50000的词。后来试了一发就过了。哈哈。枚举没一个单词，将单词拆为2半，如果2半都出现过，那就是要求的。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

struct trie

{

    trie *next[];

    int flag;

};

trie *root;

void init()

{

    int i;

    root=(trie*)malloc(sizeof(trie));

    for(i=;i<;i++)

        root->next[i]=NULL;

    root->flag=;

}

void insert(char *str)

{

    int i,j,len=strlen(str);

    trie *p=root,*q;

    for(i=;i<len;i++)

    {

        int id=str[i]-'a';

        if(p->next[id]==NULL)

        {

            q=(trie*)malloc(sizeof(trie));

            for(j=;j<;j++)

                q->next[j]=NULL;

            q->flag=;

            p->next[id]=q;

        }

        p=p->next[id];

        if(i==len-)

        {

            p->flag=;

        }

    }

}

int query(char *str)

{

    int i,j,len=strlen(str);

    trie *p=root;

    for(i=;i<len;i++)

    {

        int id=str[i]-'a';

        if(p->next[id]==NULL)

            return ;

        p=p->next[id];

    }

    if(p->flag>)

        return ;

    return ;

}

char str[][];

int main()

{

    int i,j,count=;

    int flag;

    init();

    while(gets(str[count]))

    {

        if(strcmp(str[count],"")==)break;

        insert(str[count]);

        count++;

    }

    for(i=;i<count;i++)

    {

        if(strlen(str[i])==)continue;

        char s1[],s2[];

        int l1,l2,k;

        int l=strlen(str[i]);

        for(j=;j<l;j++)//枚举单词，将单词一分为二，查询是否都出现。如果是这个单词就ok了。

        {

            flag=;

            l1=l2=;

            for(k=;k<j;k++)//左子串

            {

                s1[l1]=str[i][k];

                l1++;

            }

            s1[l1]='\0';

            for(k=j;k<l;k++)//右边子串

            {

                s2[l2]=str[i][k];

                l2++;

            }

            s2[l2]='\0';

            if(query(s1)&&query(s2))//查询

            {

                flag=;

                break;

            }

        }

        if(flag)

            printf("%s\n",str[i]);

    }

    return ;

}