首页 > 代码库 > hdu1251 统计难题

hdu1251 统计难题

2024-08-15 17:40:52   219人阅读

地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=1251

题目：

统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 35141    Accepted Submission(s): 13175


Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
 

 

Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.
 

 

Output
对于每个提问,给出以该字符串为前缀的单词的数量.
 

 

Sample Input
banana
band
bee
absolute
acm
 
ba
b
band
abc
 

 

Sample Output
2
3
1
0
 

 思路：Trie树，每个节点记录以此为前缀的单词的数量

代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXNUM 26//定义字典树结构体typedef struct Trie{    int cnt;    Trie *next[MAXNUM];}Trie;//声明一个根Trie *root;//初始化该根void init(){    root = (Trie *)malloc(sizeof(Trie));    root->cnt=0;    for(int i=0;i<MAXNUM;i++)    root->next[i]=NULL;}//对该字典树的插入单词操作void insert(char *word){    Trie *tem = root;    while(*word!=‘\0‘)    {        if(tem->next[*word-‘a‘]==NULL)        {            Trie *cur = (Trie *)malloc(sizeof(Trie));            for(int i=0;i<MAXNUM;i++)                cur->next[i]=NULL;            cur->cnt=0;            tem->next[*word-‘a‘]=cur;        }        tem = tem->next[*word-‘a‘];        tem->cnt++;        word++;    }}//查询一个单词的操作int search(char *word){    Trie *tem = root;    for(int i=0;word[i]!=‘\0‘;i++)    {        if(tem==NULL||tem->next[word[i]-‘a‘]==NULL)            return 0;        tem=tem->next[word[i]-‘a‘];    }    return tem->cnt;}int main(void){    init();    //freopen("in.txt","r",stdin);    char ss[11];    while(gets(ss)&&strlen(ss))        insert(ss);    while(~scanf("%s",ss))        printf("%d\n",search(ss));    return 0;}

 

hdu1251 统计难题


联系
我们