首页 > 代码库 > 字典树模板 [HDU 1251] 统计难题

字典树模板 [HDU 1251] 统计难题

统计难题

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


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

 

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

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

 

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

 

Sample Input
bananabandbeeabsoluteacmbabbandabc
 

 

Sample Output
2310
 

 

Author
Ignatius.L
 

字典树模板、= =

指针版、140MS

#include<iostream>#include<cstdio>#include<cstring>using namespace std;struct node{    node *next[26];    int val;};node *root;int getid(char ch) { return ch-a;}void Insert(char *s){    node *pre=root,*now;    for(int i=0;s[i]!=\0;i++)    {        int id=getid(s[i]);        now=pre->next[id];        if(!now)        {            now=new node;            memset(now,0,sizeof(node));            pre->next[id]=now;        }        now->val++;        pre=now;    }}int Find(char *s){    node *pre=root,*now;    for(int i=0;s[i]!=\0;i++)    {        int id=getid(s[i]);        now=pre->next[id];           if(!now) return 0;        pre=now;    }    return pre->val;}int main(){    char str[15];    root=new node;    memset(root,0,sizeof(node));    while(gets(str)&&strlen(str))    {        Insert(str);    }    while(gets(str))    {        printf("%d\n",Find(str));    }    return 0;}

数组版,62MS

#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define N 1000010int sz;int val[N];int ch[N][26];void init(){    sz=1;    memset(ch[0],0,sizeof(ch[0]));}int getid(char ch) { return ch-a;}void Insert(char *s){    int pre=0,now;    for(int i=0;s[i]!=\0;i++)    {        int id=getid(s[i]);        now=ch[pre][id];        if(!now)        {            val[sz]=0;            memset(ch[sz],0,sizeof(sz));            ch[pre][id]=sz;            now=sz;            sz++;        }        val[now]++;        pre=now;    }}int Find(char *s){    int pre=0,now;    for(int i=0;s[i]!=\0;i++)    {        int id=getid(s[i]);        now=ch[pre][id];        if(!now) return 0;        pre=now;    }    return val[pre];}int main(){    char s[15];    init();    while(gets(s) && strlen(s))    {        Insert(s);    }    while(gets(s))    {        printf("%d\n",Find(s));    }    return 0;}

 

字典树模板 [HDU 1251] 统计难题