首页 > 代码库 > HDU 1251 统计难题

HDU 1251 统计难题

2024-10-17 09:50:38   214人阅读

统计难题

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


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

 

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

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

 

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

 

Sample Input
bananabandbeeabsoluteacmbabbandabc
 

 

Sample Output
2310
 

 

Author
Ignatius.L
 

 


Recommend
Ignatius.L   |   We have carefully selected several similar problems for you:  1075 1247 1671 1298 1800 
trie 树，求前缀数量之和，挺裸的
#include<cstdio>#include<cstring>using namespace std;#define N 500000struct node{    bool have;    int son[26];    int cnt;    int acnt;    node(){        have=0;        cnt=0;        acnt=0;        memset(son,0,sizeof(son));    }}trie[N]; int num;void insert(char *s){    int pos=0,len=strlen(s);    int fa=0;    for(int i=0;i<len;++i)    {        pos=s[i]-‘a‘;        if(!trie[fa].son[pos]){            trie[fa].son[pos]=++num;        }        fa=trie[fa].son[pos];        trie[fa].cnt++;    }    trie[fa].have=1;    trie[fa].acnt++;}int find(char *s){    int len=strlen (s);    int pos,fa=0;    for(int i=0;i<len;++i)    {        pos=s[i]-‘a‘;        if(!trie[fa].son[pos]){            return 0;        }        fa = trie[fa].son[pos];    }    return trie[fa].cnt;}int main(){    char word[20];    while(gets(word))    {        int len=strlen(word);        if(len==0)break;        else insert(word);    }    while(gets(word))    {        printf("%d\n",find(word));    }    return 0;}

 

HDU 1251 统计难题


联系
我们