[HDOJ1251]統計難題，hdoj1251統計難題

[HDOJ1251]統計難題，hdoj1251統計難題

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1251

 

 

統計難題

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

Problem Description Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴).  

 

Input 輸入數據的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.

注意:本題只有一組測試數據,處理到文件結束.  

 

Output 對於每個提問,給出以該字符串為前綴的單詞的數量.  

 

Sample Input banana band bee absolute acm ba b band abc  

 

Sample Output 2 3 1 0     字典樹，這個寫得不好，因為new的時候很耗費內存。用G++編譯的時候還爆MLE了。C++過的。具體做法就是直接在向字典樹插入字符的時候在對應位置的節點加1，表示當前節點又被走過了1次。查找的時候輸出對應字串末位字符的cnt值就可以了。注意處理沒有該詞的情況。    

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 
13 using namespace std;
14 
15 char str[11];
16 typedef struct Node {
17     Node *next[26];
18     int cnt;
19     Node() {
20         cnt = 0;
21         for(int i = 0; i < 26; i++) {
22             next[i] = NULL;
23         }
24     }
25 }Node;
26 
27 void insert(Node *p, char *str) {
28     for(int i = 0; str[i]; i++) {
29         int t = str[i] - 'a';
30         if(p->next[t] == NULL) {
31             p->next[t] = new Node;
32         }
33         p = p->next[t];
34         p->cnt++;
35     }
36 }
37 
38 int find(Node *p, char *str) {
39     for(int i = 0; str[i]; i++) {
40         int t = str[i] - 'a';
41         p = p->next[t];
42         if(!p) {
43             return 0;
44         }
45     }
46     return p->cnt;
47 }
48 
49 int main() {
50     Node *root = new Node();
51     while(gets(str) && strlen(str)) {
52         insert(root, str);
53     }
54     while(gets(str)) {
55         int ans = find(root, str);
56         printf("%d\n", ans);
57     }
58     return 0;
59 }