C++統計難題hdu 1251

2692 ワード

統計上の課題
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