HDU1251 统计难题

描述

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

输入

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.

输出

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

样例

输入

banana
band
bee
absolute
acm

ba
b
band
abc

输出

2
3
1
0

思路

字典树模板题

用 $s [0] == 0$

代码

 1 /*
 2  * =========================================================================
 3  *
 4  *       Filename:  hdu1251.cpp
 5  *
 6  *           Link:  http://acm.hdu.edu.cn/showproblem.php?pid=1251
 7  *
 8  *        Version:  1.0
 9  *        Created:  2018/08/29 11时40分08秒
10  *       Revision:  none
11  *       Compiler:  g++
12  *
13  *         Author:  杜宁元 (https://duny31030.top/), duny31030@126.com
14  *   Organization:  QLU_浪在ACM
15  *
16  * =========================================================================
17  */
18 #include <bits/stdc++.h>
19 using namespace std;
20 #define clr(a, x) memset(a, x, sizeof(a))
21 #define rep(i,a,n) for(int i=a;i<=n;i++)
22 #define pre(i,a,n) for(int i=a;i>=n;i--)
23 #define ll long long
24 #define max3(a,b,c) fmax(a,fmax(b,c))
25 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
26 const double eps = 1e-6;
27 const int INF = 0x3f3f3f3f;
28 const int mod = 1e9 + 7;
29 const int N = 1000010;
30 struct node
31 {
32     int next[27];
33 }trie[N];
34 int num[N];   // 以某一字符串为前缀的单词的数量
35 int tot = 1;
36 char s[20];
37 void add(char a[])
38 {
39     int i,now = 0;
40     int len = strlen(a);
41     for(i = 0;i < len;i++)
42     {
43         int tmp = a[i]-'a'+1;
44         int next = trie[now].next[tmp];
45         if(!next)   // 如果对应字符还没有值
46             trie[now].next[tmp] = tot++;
47         now = trie[now].next[tmp];
48         num[now]++;
49     }
50 }
51 
52 int query(char a[])
53 {
54     int len = strlen(a);
55     int now = 0,i;
56     for(i = 0;i < len;i++)
57     {
58         int tmp = a[i]-'a'+1;
59         if(trie[now].next[tmp] == 0)
60             return 0;
61         now = trie[now].next[tmp];
62     }
63     return num[now];
64 }
65 
66 int main()
67 {
68     ios
69 #ifdef ONLINE_JUDGE 
70 #else 
71         freopen("in.txt","r",stdin);
72     // freopen("out.txt","w",stdout); 
73 #endif
74     while(gets(s))
75     {
76         if(!s[0])
77             break;
78         add(s);
79     }
80     while(gets(s))
81     {
82         printf("%d
",query(s));
83     }
84     fclose(stdin);
85     // fclose(stdout);
86     return 0;
87 }