hdu 1251 统计难题 (字典树)

统计难题

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 15844 Accepted Submission(s): 6777

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana

band

bee

absolute

acm

band

abc

Sample Output

2 3 1 0

Author

Ignatius.L

Recommend

Ignatius.L | We have carefully selected several similar problems for you: 1298 2846 1305 3460 1274

比较简单的字典树。

直接模板都可以过。

 1 //140MS    43828K    1134 B    G++
 2 #include<stdio.h>
 3 #include<string.h>
 4 struct node{
 5     int cnt;
 6     node *next[27];
 7     node(){
 8     cnt=0;
 9     memset(next,0,sizeof(next));
10     }
11 };
12 void insert(node *root,char s[])
13 {
14     int i=0;
15     node *p=root;
16     while(s[i]){
17         int j=s[i++]-'a';
18         if(p->next[j]==NULL) p->next[j]=new node();
19         p=p->next[j]; 
20         p->cnt+=1;
21         //printf("**%d
",p->cnt);
22     }
23 }
24 int judge(node *root,char s[])
25 {
26     int i=0;
27     node *p=root;
28     int flag=0;
29     while(s[i]){
30         int j=s[i++]-'a';
31         if(p->next[j]==NULL){
32             flag=0;break;
33         }
34         p=p->next[j];
35         flag=p->cnt;
36     }
37     return flag; 
38 }
39 int main(void)
40 {
41     node *root=new node();
42     char word[10];
43     char cur[10];
44     //freopen("C:\Users\Administrator\Desktop\in.txt","r",stdin);
45     //freopen("C:\Users\Administrator\Desktop\out.txt","w",stdout);
46     while(gets(word)){
47         if(strcmp(word,"")==0) break;
48         insert(root,word);
49     }
50     while(gets(cur)){
51         printf("%d
",judge(root,cur));
52     }
53     return 0;
54 }