5.2.2 统计难题

统计难题

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)

Total Submission(s): 207 Accepted Submission(s): 126

Problem Description

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

Input

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

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

Output

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

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

思路：Trie或者map，学了两天才明白了trie，其实trie本身很好懂，我的主要时间是花在学习指针和链表上了。

每读入一个单词，在插入时就顺便把前缀的个数加上，这道题就解决了。

另：推荐网站。学习链表和指针：http://see.xidian.edu.cn/cpp/biancheng/view/160.html

trie的话 http://zh.wikipedia.org/wiki/Trie http://dongxicheng.org/structure/trietree/ 的介绍不错

http://blog.163.com/mageng11@126/blog/static/14080837420119544046207/ 也很不错

290613

2013-02-17 11:31:29

Accepted

5.2.2

140MS

43868K

1150B

G++

cssystem

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <string>
 7 using namespace std;
 8 
 9 struct node
10 {
11     int cnt;
12     node *ch[26];
13     node ()
14     {
15         cnt=0;
16         memset(ch,0,sizeof(ch));
17     }
18 };
19 
20 int l,x;
21 char s[30];
22 
23 node *root=new node;
24 node *cur,*cur1,*newnode;
25 
26 void close()
27 {
28     exit(0);
29 }
30 
31 void insert()
32 {
33     cur=root;
34     l=strlen(s);
35     for (int i=0;i<l;i++)
36     {
37         if (s[i]<97 || s[i]>122) break;
38         x=s[i]-'a';
39         if (cur->ch[x]!=NULL)
40         {
41             cur=cur->ch[x];
42             ++(cur->cnt);
43         }
44         else
45         {
46             newnode=new node;
47             ++(newnode->cnt);
48             cur->ch[x]=newnode;
49             cur=newnode;
50         }
51     }
52 }
53 
54 int find()
55 {
56     cur=root;
57     l=strlen(s);
58     for (int i=0;i<l;i++)
59     {
60         if (s[i]<97 || s[i]>122) break;
61         x=s[i]-'a';
62         if (cur->ch[x]==NULL)
63             return 0;
64         else cur=cur->ch[x];
65     }
66     return cur->cnt;
67 }
68 
69 void init ()
70 {
71    while (fgets(s,30,stdin))
72     {
73         if (strlen(s)<=1 && (s[0]<97 || s[0]>124) )
74             break;
75         insert();
76         memset(s,'\0',sizeof(s));
77     }
78     while (fgets(s,30,stdin))
79     {
80         printf("%d\n",find());
81     }
82 }
83 
84 int main ()
85 {
86     init();
87     close();
88     return 0;
89 }