HDU 2846 Repository

发表于   |   分类于   |     |   阅读次数

题目描述

Description

When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.

Input

There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it’s length isn’t beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.

Output

For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.

Sample Input

20
ad
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s

Sample Output

0
20
11
11
2

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2846

解题思路

题目大概的意思就是给出P个单词，Q种询问，每次询问一个字符串s，输出包含s的字串的字符串共有多少个。
这道题是一个字典树的变形题，和普通的插入不同，我们需要将每个字符串分成不同的字串，然后将他们插入到字典树中。例如abcd，我们需要将其分成abcd，bcd，cd，d，这样就保证将一个字符串分解成了不同的前缀，我们就可以根据输入的查询字串进行查询了。但是，这样还有一个BUG，如果遇到了类似于abab这样的字符串，那么就可能被分成两个以ab为前缀的字符串。所以，对于每一个完整的字符串，我们需要对其进行编号，假如遇到重复前缀的字符串，并且这个编号已经存在了的话，节点的数值就不+1，因此就能通过不同的前缀来判断字符串的数量了。

AC代码

56368K/109MS/G++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cstring>

struct TrieTree
{
    int ID;
    int cnt;
    int node[26];
    TrieTree()
    {
        cnt = 0;
        memset(node, 0, sizeof(node));
    }
} ch[500000];

int sz = 0;
void insertion(char *s, int x)
{
    int c, u = 0, len = strlen(s);
    for (int i = 0; i < len; i++)
    {
        c = s[i] - 'a';
        if (ch[u].node[c] == 0)
        {
            ch[u].node[c] = ++sz;
            u = sz;
        }
        else
        {
            u = ch[u].node[c];
        }
        if (ch[u].ID != x)
        {
            ch[u].cnt++;
        }
        ch[u].ID = x;
    }
}

int query(char *s)
{
    int c, u = 0, len = strlen(s);
    for (int i = 0; i < len; i++)
    {
        c = s[i] - 'a';
        if (ch[u].node[c] == 0) return 0;
        u = ch[u].node[c];
    }
    return ch[u].cnt;
}

char str[21];
int main()
{
    int n, q;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", str);
        int len = strlen(str);
        for (int j = 0; j < len; j++)
        {
            insertion(str + j, n - i);
        }
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++)
    {
        scanf("%s", str);
        printf("%d\n", query(str));
    }
    return 0;
}