C++統計難題hdu 1251
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
入力データの第1部は1枚の単語表で、1行ごとに1つの単語、単語の長さは10を超えないで、それらは先生がIgnatiusに渡して統計した単語を代表して、1つの空行は単語表の終わりを代表します.第2部は一連の質問で、各行は1つの質問で、各質問はすべて1つの文字列です.
注意:本題はテストデータのセットだけで、ファイルが終わるまで処理します.
Output
各質問に対して、その文字列を接頭辞とする単語の数を与える.
Sample Input
banana
band
bee
absolute
acm
ba
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
"); return; } p = p->next[s[i]-'a']; } printf("%d
",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