hdu 1251 統計難題

題目連結： 點我點我~

統計難題 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others) Total Submission(s): 18175    Accepted Submission(s): 7957 Problem Description Ignatius最近遇到一個難題,老師交給他很多單詞(隻有小寫字母組成,不會有重複的單詞出現),現在老師要他統計出以某個字元串為字首的單詞數量(單詞本身也是自己的字首). Input 輸入資料的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字元串. 注意:本題隻有一組測試資料,處理到檔案結束. Output 對于每個提問,給出以該字元串為字首的單詞的數量. Sample Input banana band bee absolute acm ba b band abc Sample Output 2 3 1 0     題意：找出同樣字首的字元串個數，輸出；    該題是一道标準的用字典樹的題目，字典樹就是由字元組成的一棵樹. 隻要給每個節點賦上支路數，就可以表示同樣的字首字元串個數了。 套了模闆。。。。。 #include <cstdio> #include <iostream> #include <cstring> using namespace std; struct node { struct node *br[26]; int num; }; node *root; void trie_init()//字典樹清空 { root=new node; root->num=0; for(int i=0;i<26;i++) { root->br[i]=NULL; } } void trie_insert(char str[])//加入字典樹 { int len=strlen(str); node *s=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(s->br[id]==NULL) { node *t=new node; for(int j=0;j<26;j++) { t->br[j]=NULL; } t->num=0; s->br[id]=t; } s=s->br[id]; s->num++; } } int trie_find(char str[])//在字典樹中查找 { int len=strlen(str); node *s; s=root; int count=0; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(s->br[id]==NULL) return 0; else { s=s->br[id]; count=s->num; } } return count; } int main() { char str[15]; trie_init(); while(gets(str),strcmp(str,"")) { trie_insert(str); } while(gets(str)) { int res=trie_find(str); printf("%d\n",res); } return 0; }