首页 > 代码库 > HDU 1251 统计难题
HDU 1251 统计难题
统计难题
Time Limit: 2000ms
Memory Limit: 65535KB
This problem will be judged on HDU. Original ID: 125164-bit integer IO format: %I64d Java class name: Main
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
bananabandbeeabsoluteacmbabbandabc
Sample Output
2310
解题：trie
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 struct trie{18 int wd[27],cnt;19 trie(){20 memset(wd,-1,sizeof(wd));21 cnt = 0;22 }23 };24 trie dic[500000];25 int tot = 1;26 void insertWd(int root,char *s){27 for(int i = 0; s[i]; i++){28 if(dic[root].wd[s[i]-‘a‘] == -1){29 dic[root].wd[s[i]-‘a‘] = tot++;30 }31 root = dic[root].wd[s[i]-‘a‘];32 dic[root].cnt++;33 }34 }35 int query(int root,char *s){36 for(int i = 0; s[i]; i++){37 if(dic[root].wd[s[i]-‘a‘] == -1) return 0;38 root = dic[root].wd[s[i]-‘a‘];39 }40 return dic[root].cnt;41 }42 char str[20000];43 int main() {44 int root = 0;45 while(gets(str) && str[0]) insertWd(root,str);46 while(gets(str) && str[0]) printf("%d\n",query(root,str));47 return 0;48 }
HDU 1251 统计难题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。