统计难题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 2947 Accepted Submission(s): 1038
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
#include<stdio.h> #include<string.h> #include<stdlib.h> struct Tree { int n; Tree *p[26]; }head; void chushihua(Tree &a) { int i; a.n=1; for(i=0;i<26;i++) a.p[i]=NULL; } void addtree(char a[]) { int i; int n; Tree *term=&head; n=strlen(a); for(i=0;i<n;i++) { if(term->p[a[i]-'a']==NULL) { term->p[a[i]-'a']=(Tree*)malloc(sizeof(Tree)); term=term->p[a[i]-'a']; chushihua(*term); } else { term=term->p[a[i]-'a']; (term->n)++; } } } int findtree(char a[]) { int i; int n; Tree *term=&head; n=strlen(a); for(i=0;i<n;i++) { if(term->p[a[i]-'a']==NULL)return(0); term=term->p[a[i]-'a']; } return(term->n); } int main() { //freopen("in.txt","r",stdin); char str[12]; chushihua(head); while(1) { gets(str); if(str[0]==0)break; addtree(str); } while(gets(str)) { printf("%d\n",findtree(str)); } return(0); }
相关推荐
功能: 通过字典树等算法模拟了一个输入法频率提示工具。 原理: 没记错的话是用的字典树频率的统计方式做的。
字典树代码dictionary,包含数据结构和测试例程。
字典树,java语言 字典树,trie 每个节点26个子节点
acm字典树模板!acm字典树模板!acm字典树模板!acm字典树模板!
ACM Trie树 模板,字典树模板,数据结构
字典树的实现
将一些大型的英文文件建立一个结构来实现查找与分析
java是实现的快速单词检错程序,内部算法使用字典树匹配。 开发环境netbeans
集美大学数据结构课程设计 字典树 集美大学数据结构课程设计 字典树 集美大学数据结构课程设计 字典树 集美大学数据结构课程设计 字典树 集美大学数据结构课程设计 字典树 集美大学数据结构课程设计 字典树 集美大学...
用C语言实现的字典树算法,用C语言实现的字典树算法。
自己写的字典树简单实现代码,实现了插入和查找功能。
字典树与KMP的ppt课件 TJRAC_ACM内部使用
字典树,文档,增删改,排序,输出字典所有单词及意思
本文描述了字典树功能、应用及其实现,原本以为字典树是什么高深的东西,看了这个,发现也就是那样。。。
字典树:又称为Trie,是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构;一棵m度的Trie树或者为空,或者由m棵m度的Trie树构成。
可变长数组和字典树Java代码实现。比较容易复制和学习。
TJRAC_ACM 字典树KMP优先队列学习课件
字典树的模版,想学习的自己亲自把代码打一下就可以了。
Java实现字典树TrieTree,可用于计算出四六级试题的高频词.
这是本人在ACM路上总结的比较有代表性的字典树的问题,希望能给ACMER带来帮助