hdu 1251 (Trie水题）

统计难题

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

Problem Description

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

Input

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

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

Output

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

Sample Input

banana band bee absolute acm ba b band abc

Sample Output

2 3 1 0

Author

Ignatius.L

Recommend

Ignatius.L | We have carefully selected several similar problems for you: 1075 1247 1671 1298 1800

这题就是Trie水题，纯练手用的。但是题目比较坑没给你单词书目。目测十万可过。下面是套模板的Trie:

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #define clr(x) memset(x,0,sizeof(x))
  5 #define clrmin(x) memset(x,-1,sizeof(x))
  6 using namespace std;
  7 struct node
  8 {
  9     int lt,rt;
 10     int val;
 11     int num;
 12     char *c;
 13 };
 14 struct Trie
 15 {
 16     int head,len;
 17     node tr[1000010];
 18     Trie () { clr(tr); head=0; len=1;}
 19     void init()
 20     {
 21         clr(tr); 
 22         head=0;
 23         len=1;
 24         return ;
 25     }
 26     int newnode(char *c)
 27     {
 28         if(!head)
 29         {
 30             head=len;
 31         }
 32         tr[len].c=c;
 33         return len++;
 34     }
 35     void push(int fa,int now,char *str)
 36     {
 37         int p;
 38         if(!now)
 39         {
 40             now=newnode(str);
 41             tr[fa].lt=now;
 42             tr[now].num++;
 43             if(str[1]=='')
 44             {
 45                 tr[now].val++;
 46             }
 47             else
 48                 push(now,0,str+1);
 49             return ;
 50         }
 51         while(now && *tr[now].c!=*str)
 52         {
 53             p=now;
 54             now=tr[now].rt;
 55         }
 56         if(!now)
 57         {
 58             now=newnode(str);
 59             tr[p].rt=now;
 60             tr[now].num++;
 61         }
 62         else
 63             tr[now].num++;
 64         if(str[1]=='')
 65         {
 66             tr[now].val++;
 67         }
 68         else
 69             push(now,tr[now].lt,str+1);
 70         return;
 71     }
 72     int found(int now,char *str)
 73     {
 74         while(now && *tr[now].c!=*str)
 75         {
 76             now=tr[now].rt;
 77         }
 78         if(!now)
 79             return 0;
 80         else
 81             if(strlen(str)==1)
 82                 return tr[now].num;
 83             else
 84                 return found(tr[now].lt,str+1);
 85     }
 86 }tree;
 87 char s[1000010][20],str[20];
 88 int main()
 89 {
 90     int n=0;
 91     tree.init();
 92     while(fgets(str,100,stdin) && strcmp(str,"
")!=0)
 93     {
 94         str[strlen(str)-1]='';
 95         strcpy(s[n++],str);
 96         tree.push(0,tree.head,s[n-1]);
 97     }
 98     while(fgets(str,100,stdin)!=NULL)
 99     {
100         str[strlen(str)-1]='';
101         printf("%d
",tree.found(tree.head,str));        
102     }
103     return 0;
104 }