统计难题

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

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana

band

bee

absolute

acm

band

abc

Sample Output

思路:Trie树，很早以前写过，但代码写的太屎，今天做别人比赛遇到了，就重写了一次。

 #include<cstdio>

 #include<string>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 class Node{

     public:

         int cnt;

         Node *child[];

         Node(){

             cnt  =;

             for(int i = ;i < ;i ++)

                 child[i] = NULL;

         }

 };

 Node *root = new Node();

 void Update(char *str){

     Node *tmp = root;

     while(*str != '\0'){

         if(tmp->child[*str - 'a'] == NULL){

             Node *p = new Node();

             tmp->child[*str - 'a'] = p;

         }

         tmp = tmp->child[*str - 'a'];

         tmp->cnt++;

         str++;

     }

 }

 int Getresult(char *str){

     Node *tmp = root;

     while(*str != '\0'){

         if(tmp->child[*str - 'a'] == NULL) return ;

         tmp = tmp->child[*str - 'a'];

         str++;

     }

     return tmp->cnt;

 }

 int main(){

     char str[];

     while(cin.getline(str,) && strcmp(str,"")) Update(str);

     while(~scanf("%s",str)) printf("%d\n",Getresult(str));

     return ;

 }

巴特西

HDU --1251

统计难题

最新文章

热门文章