首页 > 代码库 > hdu 1251 统计难题
hdu 1251 统计难题
统计难题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)Total Submission(s): 22668 Accepted Submission(s): 9546
Problem Description
Ignatius近期遇到一个难题,老师交给他非常多单词(仅仅有小写字母组成,不会有反复的单词出现),如今老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每一个提问都是一个字符串.
注意:本题仅仅有一组測试数据,处理到文件结束.
注意:本题仅仅有一组測试数据,处理到文件结束.
Output
对于每一个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
曾经写过这道题,是用字典树,可是非常easy超时,。下边的是C++的map,这么短效并且执行也非常快
学习一下,map是一个非常好的容器
2015,7,24
#include <iostream> #include <map> #include <cstring> using namespace std; int main(){ int i,len; char str[10]; map<string, int> m; while(gets(str)){ len=strlen(str); if(!len) break; for(i=len;i>0;i--){ str[i] = '\0'; m[str]++; } } while(gets(str)) cout<<m[str]<<endl; return 0; } //字典树 #include<stdio.h> #include<string.h> #include<malloc.h> #define fun(a) (a-'a') struct Node { int num; struct Node *child[26]; } *p,*q; void CreatTrie(struct Node *root,char *s,int n) { int i,j,m; struct Node *head=root; for(i=0;i<n;i++) { m=fun(s[i]); if(head->child[m]) { head=head->child[m]; head->num++; } else { p=(struct Node *)malloc(sizeof(struct Node)); p->num=1; for(j=0;j<26;j++) p->child[j]=NULL; head->child[m]=p; head=head->child[m]; } //printf("%d %d\n",m,head->num); } } void Find(struct Node *root,char *s,int n) { int i,m; struct Node *head=root; for(i=0;i<n;i++) { m=fun(s[i]); if(head->child[m]) head=head->child[m]; else break; } if(i==n) printf("%d\n",head->num); else printf("0\n"); } void dele(struct Node *root) //释放整个字典树占的堆区空间 { int i; for(i=0;i<26;i++){ if(root->child[i]) dele(root->child[i]); } free(root); } int main() { char s[20]; int n,m,i,j,k; struct Node *root; root=(struct Node *)malloc(sizeof(struct Node)); root->num=0; for(i=0;i<26;i++) root->child[i]=NULL; while(gets(s)) { n=strlen(s); if(n==0) break; CreatTrie(root,s,n); } while(scanf("%s",s)!=EOF) { n=strlen(s); Find(root,s,n); } dele(root); return 0; }
hdu 1251 统计难题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。