HDU-1251-统计难题

统计难题

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

Problem Description

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

Input

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

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

Output

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

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

Author

Ignatius.L

法一：字典树（占空间）

法二：map

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int kind = 26;
 5 struct Treenode
 6 {
 7     size_t cnt;
 8     Treenode* next[kind];
 9     Treenode()
10     {
11         cnt = 1;
12         for(int i=0;i<kind;i++)
13             next[i] = NULL;
14     }
15 };
16 void insert(Treenode *&root,char* word)
17 {
18     Treenode *location = root;
19     int i=0,branch=0;
20     if(location==NULL)
21     {
22         location = new Treenode();
23         root = location;
24     }
25     while(word[i])
26     {
27         branch = word[i] - 'a';
28         if(location->next[branch])
29             location->next[branch]->cnt++;
30         else
31         {
32             location->next[branch] = new Treenode();
33         }
34         i++;
35         location = location->next[branch];
36     }
37 }
38 int search(Treenode *&root,char* word)
39 {
40     Treenode* location = root;
41     int i=0,branch = 0,ans=0;
42     while(word[i])
43     {
44         branch = word[i]-'a';
45         if(!location->next[branch])
46             return 0;
47         else
48         {
49             i++;
50             location = location->next[branch];
51             ans = location->cnt;
52         }
53     }
54     return ans;
55 }
56 int main()
57 {
58     char word[11];
59     char ask[11];
60     Treenode *root = NULL;
61     while(gets(word))
62     {
63         if(word[0]=='')
64             break;
65         insert(root,word);
66     }
67     while(gets(ask))
68         cout<<search(root,ask)<<endl;
69     return 0;
70 }

 1 #include <iostream>
 2 #include <map>
 3 #include <cstdio>
 4 #include <string.h>
 5 using namespace std;
 6 int main()
 7 {
 8     char a[11],b[11];
 9     map<string,int> cnt;
10 
11     while(gets(a))
12     {
13         if(a[0]=='')
14             break;
15         int len = strlen(a);
16         for(int i=0;i<len;i++)
17         {
18             int j;
19             for(j =0;j<=i;j++)
20             {
21                 b[j]=a[j];
22             }
23             b[j] = '';
24             string str(b);
25             cnt[str]++;
26         }
27     }
28     while(gets(b))
29     {
30         cout<<cnt[b]<<endl;
31     }
32 
33     return 0;
34 }

注：转载请注明出处