「洛谷 P2922」Secret Message - Trie

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．

信息是二进制的，共有 \(M\)（\(1 \le M \le 50000\)）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 \(i\) 条二进制信息的前 \(b_i\)（\(l \le b_i \le 10000\)）位，他同时知道，奶牛使用 \(N\)（\(1 \le N \le 50000\)）条暗号．但是，他仅仅知道第 \(j\) 条暗号的前 \(c_j\)（\(1 \le c_j \le 10000\)）位。

对于每条暗号 \(j\)，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中，位的总数（即 \(\sum b_i + \sum c_i\)）不会超过 \(500000\)。

解题思路

本题显然是一道字符串题，我们可以用 Trie 解决。我们可以将所有的 \(b_i\) 插入到一个 Trie 中。对于每个 \(c_i\)，我们有下列两种统计：

  • 通过查询路径统计 比暗号短的信息 的个数；
  • 通过在暗号尾部 DFS 统计 比暗号长的信息 的个数。

这里单纯的 DFS 会 TLE，加个记忆化就行了。

代码演示

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
74
75
76
77
78
#include <cstdio>
#include <cstring>

const int MAXN = 500000;

int trie[MAXN + 2][2], tot = 1;
int end[MAXN + 2];
int size[MAXN + 2];

inline void insert(int *str, int len) {
    int p = 1;
    for (int i = 0; i < len; i++) {
        int ch = str[i];
        if (trie[p][ch] == 0) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    end[p]++;
}

int getSize(int p) {
    if (size[p] != -1) return size[p];
    if (p == 0) return 0;

    size[p] = end[p];
    size[p] += getSize(trie[p][0]);
    size[p] += getSize(trie[p][1]);

    return size[p];
}

int search(int *str, int len) {
    int p = 1, cnt = 0;

    for (int i = 0; i < len; i++) {
        p = trie[p][str[i]];
        if (p == 0) return cnt;
        cnt += end[p];
    }

    cnt += getSize(trie[p][0]);
    cnt += getSize(trie[p][1]);

    return cnt;
}

int main() {
    int m, n;

    scanf("%d %d", &m, &n);

    for (int i = 0; i < m; i++) {
        int len;
        static int b[MAXN];

        scanf("%d", &len);
        for (int j = 0; j < len; j++) {
            scanf("%d", &b[j]);
        }

        insert(b, len);
    }

    memset(size, -1, sizeof(size));

    for (int i = 0; i < n; i++) {
        int len;
        static int c[MAXN];

        scanf("%d", &len);
        for (int j = 0; j < len; j++) {
            scanf("%d", &c[j]);
        }

        printf("%d\n", search(c, len));
    }

    return 0;
}