首页 > 代码库 > Hat’s Words

Hat’s Words

Hat’s Words

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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
# include<cstring>
using namespace std;
#define MAX 51000
map<string,int> m;
 string ch[MAX];
int main()
{
    char ch1[100],ch2[100];
    int i=0;

    while(cin>>ch[i])
    {
       m[ch[i++]]=1;
    }
    for(int j=0;j<i;j++)
    {
        for(int k=1;k<ch[j].size()-1;k++)
        {
             string ch1(ch[j],0,k);     //表示把ch[j]中从下标0开始连续的k个字符串赋给ch1  
             string ch2(ch[j],k,ch[j].size()-k);
            if(m[ch1]==1&&m[ch2]==1)
            {
               cout<<ch[j]<<endl;
                break;
            }
        }
    }
    return 0;
}