Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

 

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

 

/*Author: 2486Memory: 9096 KB		Time: 31 MSLanguage: G++		Result: Accepted*///这道题目思路非常easy//就是找两个单词组成还有一个单词就可#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;const int MAXN = 1000000 + 5;const int MAXM = 50000 + 5;const int INF = 0x3f3f3f3f;struct node { int v,next[30]; void init() { v = -1; memset(next, -1, sizeof(next)); }} L[MAXN];int tot;char str[MAXM][100];priority_queue
                   
                    , greater
                    
                      >P;void add(char * a, int len) { int now = 0; for(int i = 0; i < len ; i ++) { int tmp = a[i] - 'a'; int next = L[now].next[tmp]; if(next == -1) { next = ++ tot; L[next].init(); L[now].next[tmp] = next; } now = next; } L[now].v = 0;}bool querys(char * a) { int len = strlen(a); int now = 0; for(int i = 0; i < len; i ++) { int tmp = a[i] - 'a'; int next = L[now].next[tmp]; if(next == -1) return false; now = next; } return L[now].v == 0;}bool query(char * a, int len) { int now = 0; for(int i = 0; i < len; i ++) { int tmp = a[i] - 'a'; int next = L[now].next[tmp]; if(L[now].v == 0) { if(querys(a + i)) return true;//是否存在还有一个单词能够组成剩下的字符串 } now = next; } return false;}int main() { int cnt = 0, Min = INF; L[0].init(); tot = 0; //freopen("D://imput.txt", "r", stdin); while(~scanf("%s", str[cnt ++])) { add(str[cnt - 1], strlen(str[cnt - 1])); Min = min(Min, int(strlen(str[cnt - 1]))); } for(int i = 0; i < cnt ; i ++) { if(Min * 2 > strlen(str[i]))continue; if(query(str[i], strlen(str[i]))) P.push(str[i]); } string s; while(!P.empty()) {//优先队列自己主动排序也可使用set或者map s = P.top(); P.pop(); cout<
                     <