呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

hdu 1251:统计难题(字典树,经典题)

统计难题

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


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

 

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

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

 

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

 

Sample Input
banana
band
bee
absolute
acm
 
ba
b
band
abc
 

 

Sample Output
2
3
1
0
 

 

Author
Ignatius.L
 

 

Recommend
Ignatius.L   |   We have carefully selected several similar problems for you:  1075 1247 1671 1298 1800 

 
  字典树,经典题
  今早看了看资料,晚上就会做题了,真的不难,不明白自己为什么放了这么久才看。字典树还是很简单的。
  我用了2种做法给大家参考,一种是用链表存储,一种是用数组存储。
  思路
    字典树的经典应用,给你多个单词,构建字典树,然后给你一个字符串,求以这个字符串为前缀的单词的数量。
  注意
    注意如何判断空行,我用了2种方法。
    1、用strlen()计算字符串的长度,如果长度为0,说明为空行,退出输入循环。见代码一
    2、用gets()读入。读入的回车符会自动转换为NULL。所以循环读入,每次检测读入进来的字符串的第一个字符是否为NULL即可。见代码二。
  代码一(链表)
 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 
 5 struct Tire{    //字典树定义
 6     Tire* next[26];
 7     int num;    //以当前字符串为前缀的单词的数量
 8     Tire()    //构造函数
 9     {
10         int i;
11         for(i=0;i<26;i++){
12             next[i] = NULL;
13         }
14         num=0;
15     }
16 };
17 Tire root;
18 void Insert(char word[])    //将字符串word插入到字典树中
19 {
20     Tire *p = &root;
21     int i;
22     for(i=0;word[i];i++){    //遍历word的每一个字符
23         if(p->next[word[i]-'a']==NULL)    //如果该字符没有对应的节点
24             p->next[word[i]-'a'] = new Tire;    //创建一个
25         p = p->next[word[i]-'a'];
26         p->num++;
27     }
28 }
29 int Find(char word[])    //返回以字符串word为前缀的单词的数量
30 {
31     Tire *p = &root;
32     int i;
33     for(i=0;word[i];i++){    //在字典树找到该单词的结尾位置
34         if(p->next[word[i]-'a']==NULL)
35             return 0;
36         p = p->next[word[i]-'a'];
37     }
38     return p->num;
39 }
40 
41 int main()
42 {
43     char word[11];
44     while(cin.getline(word,12)){    //输入单词
45         if(strlen(word)==0 || word[0]==' ')    //如果读入字符串的长度为0或者是空格,说明读入的是空行
46             break;
47         Insert(word);
48     }
49     while(scanf("%s",word)!=EOF){
50         printf("%d\n",Find(word));    //返回word为前缀的单词的数量
51     }
52     return 0;
53 }

   代码二(数组)

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 
 5 int tire[1000010][26];    //数组形式定义字典树,值存储的是下一个字符的位置
 6 int num[1000010]={0};    //附加值,以某一字符串为前缀的单词的数量
 7 int pos = 1;
 8 
 9 void Insert(char word[])    //在字典树中插入某个单词
10 {
11     int i;
12     int c = 0;
13     for(i=0;word[i];i++){
14         int n = word[i]-'a';
15         if(tire[c][n]==0)    //如果对应字符还没有值
16             tire[c][n] = pos++;
17         c = tire[c][n];
18         num[c]++;
19     }
20 }
21 int Find(char word[])    //返回以某个字符串为前缀的单词的数量
22 {
23     int i;
24     int c = 0;
25     for(i=0;word[i];i++){
26         int n = word[i]-'a';
27         if(tire[c][n]==0)
28             return 0;
29         c = tire[c][n];
30     }
31     return num[c];
32 }
33 
34 int main()
35 {
36     char word[11];
37     while(gets(word)){
38         if(word[0]==NULL)    //空行。gets读入的回车符会自动转换为NULL。
39             break;
40         Insert(word);
41     }
42     while(gets(word))
43         printf("%d\n",Find(word));
44     return 0;
45 }

SUM

  以下是2种做法的效率对比

  第二行的是第一种做法,第一行的是第二种做法,很明显,数组做法不管是在时间,空间,代码量上都要优于链表做法。

  但是数组的不太好理解,如何取舍看各位看官的意思吧。

 

Freecode : www.cnblogs.com/yym2013

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [hdu 1251:统计难题(字典树,经典题)](http://www.yangyingming.com/article/75)**