首页 > 代码库 > Hdu 1251 统计难题
Hdu 1251 统计难题
Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
bananabandbeeabsoluteacmbabbandabc
Sample Output
2310
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 typedef struct Trie 5 { 6 int num; 7 struct Trie *next[26]; 8 bool exist; 9 }node,*trie;10 node *create()11 {12 node *a=(node *)malloc(sizeof(node));13 a->num=0;14 a->exist=false;15 memset(a->next,0,sizeof(a->next));16 return a;17 }18 void insert_(trie root,char *s)19 {20 trie a=root;21 char *p=s;22 int id;23 while(*p)24 {25 id=*p-‘a‘;26 if(a->next[id]==NULL)27 {28 a->next[id]=create();29 }30 a=a->next[id];31 p++;32 a->num+=1;33 }34 a->exist=true;35 }36 int finds(trie root,char *s)37 {38 trie a=root;39 char *p=s;40 int id;41 while(*p)42 {43 id=*p-‘a‘;44 a=a->next[id];45 ++p;46 if(a==NULL)47 {48 return 0;49 }50 }51 return a->num;52 }53 int main()54 {55 trie root=create();56 char str[12];57 bool judge=false;58 while(gets(str))59 {60 if(judge)61 {62 printf("%d\n",finds(root,str));63 }64 else65 {66 if(strlen(str)!=0)67 insert_(root,str);68 else69 judge=true;70 }71 }72 return 0;73 }
Hdu 1251 统计难题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。