首页 > 代码库 > HDU 1247 Hat’s Words

HDU 1247 Hat’s Words

2024-07-07 11:53:02   226人阅读

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<string.h>
int ch[7000010][26];
int val[7000010] ,sz=1;
char s[50005][50];
char a[50] ,b[50];
int id(char c) {return c-'a';}
void Inser(char *s) {
    int u=0;
    for(int i=0;s[i];i++) {
        int c=id(s[i]);
        if(!ch[u][c]) ch[u][c]=sz++;
        u=ch[u][c];
    }
    val[u]=1;
}
int Find(char *s )
{
    int u=0;
    for(int i=0;s[i];i++) {
        int c=id(s[i]);
        if(!ch[u][c]) return 0;
        u=ch[u][c];
    }
    if(val[u] == 1) return 1;
    else return 0;

}
int main()
{
    int k=0;
    while(~scanf("%s",s[k])) {
        Inser(s[k]);
        k++;
    }
    for(int i=0;i<k;i++) {
        int n=strlen(s[i]);
        for(int j=0; j<n-1 ;j++) {
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            int kk=0 ,aa ,bb;
            for(aa=0;aa<=j;aa++) a[aa]=s[i][aa];
            for(bb=j+1;bb<n;bb++) b[kk++]=s[i][bb];
            if(Find(a) && Find(b)) {
                puts(s[i]);
                break;
            }
        }
    }
    return 0;
}





联系
我们