統計難題

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 26646????Accepted Submission(s): 10785


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

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

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

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

Sample Input banana band bee absolute acmba b band abc
Sample Output 2 3 1 0

#include <iostream> #include <cstdio> #include <cstring> using namespace std;

struct node{int cnt;struct node *next[26];node(){cnt = 0;memset(next,0,sizeof(next));} };

node *root = NULL; void buildtrie(char *s){node *p = root;node *tmp = NULL;int l = strlen(s);for(int i = 0; i < l; i++){if(p->next[s[i]-'a'] == NULL){tmp = new node;p->next[s[i]-'a'] = tmp;}p = p->next[s[i]-'a'];p->cnt++;} }

void findtrie(char *s){node *p = root;int l = strlen(s);for(int i = 0; i < l; i++){if(p->next[s[i]-'a'] == NULL){printf("0\n");return;}p = p->next[s[i]-'a'];}printf("%d\n",p->cnt); }

int main() {char str[11];root = new node;while(gets(str)){if(strcmp(str,"") == 0)break;buildtrie(str);}while(scanf("%s",str) != EOF){findtrie(str);}return 0; }

模板 http://blog.csdn.net/piaocoder/article/details/47836559

?

總結

以上是生活随笔為你收集整理的C++统计难题hdu1251的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。