首页 > 代码库 > hdu1247 Hat’s Words

hdu1247 Hat’s Words

2024-08-15 17:33:21   218人阅读

地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=1247

题目：

Hat’s Words

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13765    Accepted Submission(s): 4927


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
 

 思路：1.用Trie树，枚举每个单词，看他是否由两个单词组成，判断过程其实就是字典树的查找。时间复杂度是O（n*len）

　　　　2.map爆一发，map哈希的复杂度不清楚，不过也是枚举每个单词是否由两个单词组成，枚举过程时间复杂度也是O（n*len），总体复杂度和Trie复杂度应该差不多。

　　　　3.我看到我的运行时间很短，可能暴力枚举加map也能过。枚举str[i]，str[j]，判断map[str[i]+str[j]]存不存在即可，不知道能过否

代码：

#include <stdio.h>#include <stdlib.h>using namespace std;#define MAXNUM 26//定义字典树结构体typedef struct Trie{    bool flag;//从根到此是否为一个单词    Trie *next[MAXNUM];}Trie;//声明一个根Trie *root;char ss[50006][100];//初始化该根void init(){    root = (Trie *)malloc(sizeof(Trie));    root->flag=false;    for(int i=0;i<MAXNUM;i++)    root->next[i]=NULL;}//对该字典树的插入单词操作void insert(char *word){    Trie *tem = root;    while(*word!=‘\0‘)    {        if(tem->next[*word-‘a‘]==NULL)        {            Trie *cur = (Trie *)malloc(sizeof(Trie));            for(int i=0;i<MAXNUM;i++)            cur->next[i]=NULL;            cur->flag=false;            tem->next[*word-‘a‘]=cur;        }        tem = tem->next[*word-‘a‘];        word++;    }    tem->flag=true;}bool search2(char *word){    Trie *tem = root;    char *p=word;    while(*p)    {        if(tem==NULL||tem->next[*p-‘a‘]==NULL)            return false;        tem=tem->next[*p-‘a‘];        p++;    }    return tem->flag;}//查询一个单词的操作bool search1(char *word){    Trie *tem = root;    for(int i=0;word[i]!=‘\0‘;i++)    {        tem=tem->next[word[i]-‘a‘];        if(tem->flag&&search2(&word[i+1]))            return 1;    }    return 0;}int main(void){    int n=1;    init();    while(~scanf("%s",ss[n]))        insert(ss[n]),n++;    for(int i=1;i<n;i++)    if(search1(ss[i]))        printf("%s\n",ss[i]);    return 0;}

 

hdu1247 Hat’s Words


联系
我们