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

Repository

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2538    Accepted Submission(s): 990

Problem Description

When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.

Input

There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it's length isn't beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.

Output

For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.

Sample Input

20 ad ae af ag ah ai aj ak al ads add ade adf adg adh adi adj adk adl aes 5 b a d ad s

Sample Output

0 20 11 11 2

Source

2009 Multi-University Training Contest 4 - Host by HDU

题意: 给出一些字符,然后寻问一个字符,在给出字符里能找到子串的个数..

代码:

 1 //#define LOCAL
 2 #include<cstdio>
 3 #include<cstring>
 4 typedef struct node
 5 {
 6    struct node *child[26];
 7    int cnt;  //作为统计
 8    int id;
 9 }Trie;
10 
11 void Insert(char *s,Trie *root,int id)
12 {
13     int pos,i;
14     Trie *cur=root,*curnew;
15     for(;*s!='\0';s++)
16     {
17         pos=*s-'a';
18       if(cur->child[pos]==NULL)
19       {
20            curnew = new Trie;
21            for( i=0; i<26;i++)
22             curnew->child[i]=NULL;
23             curnew->cnt=0;
24             curnew->id=0;
25             cur->child[pos]=curnew;
26       }
27       cur=cur->child[pos];
28       if(cur->id!=id) //避免同一个单词重复计算子串
29          {
30              cur->cnt++;
31              cur->id=id;
32          }
33     }
34 }
35 
36 int query(char *s, Trie *root)
37 {
38     int pos;
39     Trie *cur=root;
40     while(*s!='\0')
41     {
42         pos=*s-'a';
43         if(cur->child[pos]==NULL)
44             return 0;
45         cur=cur->child[pos];
46         s++;
47     }
48     return cur->cnt;
49 }
50 void del(Trie *root)
51 {
52     Trie *cur=root;
53     for(int i=0;i<26;i++)
54     {
55         if(cur->child[i]!=NULL)
56            del(cur->child[i]);
57     }
58     delete cur;
59   return ;
60 }
61 char str[22];
62 int main()
63 {
64 #ifdef LOCAL
65   freopen("test.in","r",stdin);
66 #endif
67   int n,m,i;
68   scanf("%d",&n);
69   Trie *root=new Trie;
70   for( i=0;i<26;i++)
71     root->child[i]=NULL;
72     root->cnt=0;
73   while(n--)
74   {
75       scanf("%s",str);
76       for(i=0 ; str[i]!='\0' ;i++)
77         Insert(str+i,root,n+1);
78   }
79   scanf("%d",&m);
80   while(m--)
81   {
82       scanf("%s",str);
83       printf("%d\n",query(str,root));
84   }
85   del(root);
86   return 0;
87 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

Leetcode 174 Dungeon Game

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

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

Leetcode 208 Implement Trie (Prefix Tree) 字典树

Implement a trie with insert, search, and startsWith methods. Note: You may ...

20960
来自专栏ml

hdu----(2222)Keywords Search(ac自动机)

Keywords Search Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

36270
来自专栏ml

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

Hat’s Words Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 ...

32390
来自专栏冷冷

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

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

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

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

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

32860
来自专栏Java学习123

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

37370
来自专栏ml

hdu----(1671)Phone List(Trie带标签)

Phone List Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K...

30660
来自专栏JackieZheng

漫谈可视化Prefuse(五)---一款属于我自己的可视化工具

  伴随着前期的基础积累,翻过API,读过一些Demo,总觉得自己已经摸透了Prefuse,小打小闹似乎已经无法满足内心膨胀的自己。还记得儿时看的《武状元苏乞儿...

28880
来自专栏DannyHoo的专栏

label中文字的自适应--使用masonry

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

19310

扫码关注云+社区

领取腾讯云代金券