hdu--(1247)Hat’s Words(trie树)

Hat’s Words

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

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

Author

戴帽子的

简述题意: 给你很多单词,查找能够由其中的两个单词拼合而成的单词,并按字典序输出.....

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 typedef struct node
 5 {
 6   struct node *child[26];
 7   bool tail;
 8 }Trie;
 9 char mat[50005][15];
10 void Insert(char *s,Trie *root)
11 {
12     int i,pos,j;
13     Trie *cur=root,*curnew;
14     for(i=0;s[i]!='\0';i++){
15         pos=s[i]-'a';
16          if(cur->child[pos]==NULL)
17          {
18              curnew=(Trie *)malloc(sizeof(Trie));
19              for(j=0;j<26;j++)
20              curnew->child[j]=NULL;
21              curnew->tail=false;
22              cur->child[pos]=curnew;
23          }
24          cur=cur->child[pos];
25     }
26      cur->tail=true;
27 }
28 bool check(char *s,Trie *root)
29 {
30     int i,pos;
31     Trie *cur=root;
32    for(i=0;s[i]!='\0';i++)
33    {
34      pos=s[i]-'a';
35      if(cur->child[pos]==NULL) return 0;
36       cur=cur->child[pos];
37    }
38    if(cur->tail==1)return 1;
39    return 0;
40 }
41 bool query(char *s,Trie *root)
42 {
43     int i,pos;
44     Trie *cur=root;
45     for(i=0;s[i]!='\0';i++)
46     {
47         pos=s[i]-'a';
48         if(cur->child[pos]==NULL) return 0;
49         else
50          if(cur->tail==1&&check(s+i,root))
51            return 1;
52          cur=cur->child[pos];
53     }
54     return 0;
55 }
56 int main()
57 {
58    int i=0,j;
59    #ifdef LOCAL
60    freopen("test.in","r",stdin);
61    #endif
62    Trie *root=(Trie *)malloc(sizeof(Trie));
63       root->tail=0;
64      for(j=0;j<26;j++)
65        root->child[j]=NULL;
66    while(scanf("%s",mat[i])!=EOF){
67      Insert(mat[i],root);
68      i++;
69    }
70   for(j=0;j<i;j++)
71   {
72       if(query(mat[j],root))
73         printf("%s\n",mat[j]);
74   }
75   return 0;
76 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 174 Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right...

2136
来自专栏JAVA烂猪皮

Dubbo性能调优参数及原理

其中,Constants.DEFAULT_QUEUES = 200。threads 参数配置的是业务处理线程池的最大(或核心)线程数。

2891
来自专栏吴伟祥

EhCache缓存工具类 原

参考:https://blog.csdn.net/qq_34531925/article/details/79134903

1313
来自专栏Java学习123

用PyQt实现透明桌面时钟小部件

3527
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

9286
来自专栏服务端技术杂谈

dubbo源码学习笔记----RPC

RpcContext 整个RpcContext通过ThreadLocal维持。 public class RpcContext { private sta...

3176
来自专栏ml

hdu----(2848)Repository(trie树变形)

Repository Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K...

3608
来自专栏ml

hdu ----3695 Computer Virus on Planet Pandora (ac自动机)

Computer Virus on Planet Pandora Time Limit: 6000/2000 MS (Java/Others)    Memor...

3628
来自专栏ml

hdu----(3065)病毒侵袭持续中(AC自动机)

病毒侵袭持续中 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

3274
来自专栏冷冷

【jfinal修仙系列】扩展CacheInterceptor支持Redis缓存

jfinal内置CacheInterceptor 依赖于EhCachePlugin,是基于ehcache的。 CacheInterceptor 可以将 acti...

2126

扫码关注云+社区

领取腾讯云代金券