hdu 1247 Hat’s Words-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

hdu 1247 Hat’s Words

简介:

点击此处即可传送到 hdu 1247

                       **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

题目大意:就是给出若干个单词,找出其中能够由其它两个单词连接组合而成的单词。比如上面sample中的”ahat”能够由”a”和”hat”拼凑而成,”hatword”=”hat”+”word,当然,也不一定是非得 “hat” +”什么 “,也可以是”word” + “good”,就是这样了:给出一个例子:
Intput
a
aa
aaa
hat
word
s
hatwords

Output
aa
aaa

解题思路:Trie树,将单词拆分,具体代码上给出详细注释:
上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
const int maxn = 26;
struct Trie//结点声明
{
    struct Trie *next[maxn];//孩子分支
    bool isStr;//标记是否构成单词
};

void Insert(Trie *root,const char *s)//将单词s插入Trie树
{
    if(root==NULL || *s=='\0')
        return;
    //int i;
    Trie *p = root;
    while(*s != '\0')
    {
        if(p->next[*s-'a'] == NULL) //如果不存在,则建立结点
        {
            Trie *tmp = (Trie*)malloc(sizeof(Trie));
            for(int i=0; i<maxn; i++)
                tmp->next[i] = NULL;
            tmp->isStr = false;
            p->next[*s-'a'] = tmp;
            p = p->next[*s-'a'];
        }
        else
            p = p->next[*s-'a'];
        s++;
    }
    p->isStr = true;//单词结束的地方标记此处可以构成一个单词
}

int Find(Trie *root, const char *s)
{
    Trie *p = root;
    while(p!=NULL && *s!='\0')
    {
        p = p->next[*s-'a'];
        s++;
    }
    return (p!=NULL && p->isStr==true);//在单词结束处的标记为true时,单词才存在
}

void Del(Trie *root)//释放整个Trie树的空间
{
    for(int i=0; i<maxn; i++)
    {
        if(root->next[i] != NULL)
            Del(root->next[i]);
    }
    free(root);
}
char s[50000][100];
char str[100];
int main()
{
    int m,n; //n为建立Trie树输入的单词数,m为要查找的单词数
    Trie *root = (Trie *)malloc(sizeof(Trie));
    for(int i=0; i<maxn; i++)
        root->next[i] = NULL;
    root->isStr = false;
    int cnt = 0;
    while(scanf("%s",str) != EOF)
    {
        strcpy(s[cnt++],str);
        Insert(root, str);
    }
    for(int i=0; i<cnt; i++)
    {
        for(int j=1; j<strlen(s[i]); j++)
        {
            char tmp1[100] = {'\0'};
            char tmp2[100] = {'\0'};
            /*strncpy函数是指(char s1,char s2, int len)三个参数,将s2的len个数
            复制给s1,但是最后要加'\0'要不然就会。。。。*/
            strncpy(tmp1, s[i], j);
            strncpy(tmp2, s[i]+j, strlen(s[i])-j);
            if(Find(root, tmp1) && Find(root, tmp2))
            {
                printf("%s\n",s[i]);
                break;
            }
        }
    }
    Del(root);
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章