HDU1251 统计难题(trie树[重做])

2019-11-08 00:48:27

字体：大中小

来源：转载

供稿：网友

统计难题Time Limit: 4000/2000 MS (java/Others) Memory Limit: 131070/65535 K (Java/Others)Total Submission(s): 37919 Accepted Submission(s): 13951PRoblem DescriptionIgnatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).Input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.注意:本题只有一组测试数据,处理到文件结束.Output对于每个提问,给出以该字符串为前缀的单词的数量.Sample InputbananabandbeeabsoluteacmbabbandabcSample Output2310trie树重做，熟悉一下,以前用字典树做一直是卡过去的,然后用了容器,现在用字典树重做一次。typedef struct Trie_tree{ int count; struct Trie_tree* next[26]; bool exist; }trieNode,*trie;trieNode* createTrieNode(){ trieNode* node=(trieNode*)malloc(sizeof(trieNode)); node->count=0; node->exist=false; mes(node->next,0); return node;}void insert(trie root,char* str){ trie node=root; char *p=str; int id; while(*p) { id=*p-'a'; if(node->next[id]==NULL){ node->next[id]=createTrieNode(); } node = node->next[id]; ++p; node->count += 1; } node->exist = true;}int search(trie root,char* str){ trie node=root; char *p=str; int id; while(*p) { id=*p-'a'; node=node->next[id]; ++p; if(node == NULL){ return 0; } } return node->count;}int main(){ trie root=createTrieNode(); char str[11]; bool flag=false; while(gets(str)){ if(flag){ printf("%d/n",search(root,str)); }else{ if(strlen(str)!=0){ insert(root,str); }else{ flag=true; } } } return 0;}

上一篇：Dijkstra算法、Floyd算法的区别与联系，并由此谈到greedy和DP

下一篇：【LeetCode 12】 Integer to Roman

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注