# 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

Sample Output

0 20 11 11 2

Source

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

### hdu----（2222）Keywords Search（ac自动机）

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

36270

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

37370

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

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

30660

### 漫谈可视化Prefuse（五）---一款属于我自己的可视化工具

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

28880

19310