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): 13851 Accepted Submission(s): 4966
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枚の辞書表に対して、順方向と逆方向の2本の辞書ツリーを確立し、順方向にすべての単語を列挙し、逆方向を取って2つの単語が現在の列挙を構成する単語があるかどうかを判断する.
コード#コード#

#include
#include
#include
#include
using namespace std;
//       
const int maxn=27;
struct Trie
{
    Trie *ch[maxn];
    bool flag;//                  
};
Trie root_1,root_2;//            
bool flag_1[maxn],flag_2[maxn];
char str_1[maxn],str_2[maxn];
void Insert_1(char *str)
{
    Trie *p=&root_1,*q;
    int len=strlen(str);
    for(int i=0; iint point=str[i]-'a';
        if(p->ch[point]==NULL)
        {
            q=(Trie *)malloc(sizeof(Trie));
            q->flag=false;
            for(int j=0; jch[j]=NULL;
            p->ch[point]=q;
        }
        p=p->ch[point];
    }
    p->flag=true;//                 
}
void Insert_2(char *str)
{
    Trie *p=&root_2,*q;
    int len=strlen(str);
    for(int i=0; iint point=str[i]-'a';
        if(p->ch[point]==NULL)
        {
            q=(Trie *)malloc(sizeof(Trie));
            q->flag=false;
            for(int j=0; jch[j]=NULL;
            p->ch[point]=q;
        }
        p=p->ch[point];
    }
    p->flag=true;//                 
}
void check_2(char *str)//            
{
    Trie *p=&root_2;
    int len=strlen(str);
    for(int i=0; iif(p->flag)
            flag_2[i]=true;
        int point=str[i]-'a';
        if(p->ch[point]==NULL)
            return;
        p=p->ch[point];
    }
}
void Getstr_2(char *str)//    
{
    int len=strlen(str);
    for(int i=0; i1]=str_1[i];
    str_2[len]='\0';
}
void DFS(Trie *from,int i)
{
    if(from->flag)
    {
        str_1[i]='\0';
        Getstr_2(str_1);
        memset(flag_2,false,sizeof(flag_2));
        check_2(str_2);
        int len=strlen(str_1);
        for(int j=1; jif(flag_1[j]&&flag_2[len-j])
            {
                printf("%s
",str_1);
                break;
            }
        }
        flag_1[i]=true;
    }
    for(int j=0; jif(from->ch[j])
        {
            str_1[i]=j+'a';
            DFS(from->ch[j],i+1);
        }
    }
    flag_1[i]=false;
}
int main()
{
    root_1.flag=false;
    root_2.flag=false;
    for(int i=0; iwhile(scanf("%s",str_1)!=EOF)
    {
        Insert_1(str_1);
        Getstr_2(str_1);
        Insert_2(str_2);
    }
    DFS(&root_1,0);
    return 0;
}