在 Trie 中储存两个信息

题目描述

Bessie is leading the cows in an attempt to escape! To do this, the cows are sending secret binary messages to each other.

Ever the clever counterspy, Farmer John has intercepted the first b_i (1 <= b_i <= 10,000) bits of each of M (1 <= M <= 50,000) of these secret binary messages.

He has compiled a list of N (1 <= N <= 50,000) partial codewords that he thinks the cows are using. Sadly, he only knows the first c_j (1 <= c_j <= 10,000) bits of codeword j.

For each codeword j, he wants to know how many of the intercepted messages match that codeword (i.e., for codeword j, how many times does a message and the codeword have the same initial bits). Your job is to compute this number.

The total number of bits in the input (i.e., the sum of the b_i and the c_j) will not exceed 500,000.

Memory Limit: 32MB

POINTS: 270

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

信息是二进制的，共有M(1≤M≤50000)条．反间谍能力很强的约翰已经部分拦截了这些信息，知道了第i条二进制信息的前bi(l《bi≤10000)位．他同时知道，奶牛使用N(1≤N≤50000)条密码．但是，他仅仅了解第J条密码的前cj(1≤cj≤10000)位．

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

在输入文件中，位的总数（即∑Bi+∑Ci）不会超过500000.

输入输出格式

输入格式

• Line 1: Two integers: M and N

• Lines 2..M+1: Line i+1 describes intercepted code i with an integer b_i followed by b_i space-separated 0’s and 1’s

• Lines M+2..M+N+1: Line M+j+1 describes codeword j with an integer c_j followed by c_j space-separated 0’s and 1’s

输出格式

• Lines 1..M: Line j: The number of messages that the jth codeword could match.

输入输出样例

输入样例#1

1
2
3
4
5
6
7
8
9
10

4 5 
3 0 1 0 
1 1 
3 1 0 0 
3 1 1 0 
1 0 
1 1 
2 0 1 
5 0 1 0 0 1 
2 1 1 

输出样例#1

1
2
3
4
5

1 
3 
1 
1 
2 

说明

Four messages; five codewords.

The intercepted messages start with 010, 1, 100, and 110.

The possible codewords start with 0, 1, 01, 01001, and 11.

0 matches only 010: 1 match

1 matches 1, 100, and 110: 3 matches

01 matches only 010: 1 match

01001 matches 010: 1 match

11 matches 1 and 110: 2 matches

解题思路

查询前缀的题很容易想到 Trie

维护两个信息 pass 和 lasts
pass 表示当前节点有多少条信息经过， lasts 表示有多少以当前节点结尾的信息（不一定没有相同的串）

插入就不说了，说说查询

查询的时候，记一下路径上lasts的和（也就是拿原信息去匹配查询信息）

首先对于每一条查询信息，都分两种情况

1. 这条信息被完美的查询完了
2. 这条信息查到一半断开了

对于第二种情况，什么都不用管，输出统计的lasts的和就行
对于第一种情况，则需要减去查询信息的最后一个节点的lasts值，加上pass值再输出

为什么呢？

这里建议画图理解

首先，如果查到一半断开了，那么答案就是用原信息去匹配查询信息的匹配数，也就是lasts的和

1
2
3
4
5
6
7
8

比如下面的例子
查询信息：
rain_air_txdy
原始信息：
rain
rain_air
rain_air_tql（这个也是没法匹配的，后几个字符不同）
那么匹配数就是2，即为答案

如果查询完了，那么说明存在能匹配查询信息的原信息，所以「用原信息去匹配查询信息的匹配数」还不够，要再加上「用查询信息去匹配原信息的匹配数」，也就是lasts的总和 + pass

有这么一种情况，就是原信息与查询信息相同，那么它在当前节点的lasts里面算了一次，在当前节点的pass又算了一次！所以要减去当前节点的lasts

1
2
3
4
5
6
7
8
9
10
11

比如下面的例子
查询信息：
rain_air_txdy
原始信息：
rain_air_txdy_tql
rain_air_txdy
答案是啥？2

注意到y这里的 pass 是2，把两条信息都算上了
但同时y这里的 lasts 也是1啊！！！
这不就重了吗，所以要减去 lasts

我觉得我说的已经够通俗易懂了吧AJ3jc8.png

代码实现

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

#include <iostream>
#include <cstring>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 500000 + 10;

struct Trie {
    struct Node {
        int pass, lasts;
        int next[2 + 1];
        
        Node() {
            pass = lasts = 0;
            memset(next, 0, sizeof next);
        }
    } node[MAXN];
    
    int cnt;
    
    Trie() {
        cnt = 0;
    }
    
    void SwitchTo(int &now, bool data) {
        if (node[now].next[data] == 0) {
            node[now].next[data] = ++cnt;
        }
        now = node[now].next[data];
    }
    bool switchTo(int &now, bool data) {
        if (node[now].next[data] == 0) return false;
        now = node[now].next[data];
        return true;
    }
} t;

int m, n;

int main() {
    IMPROVE_IO();
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) {
        int f = 0, pos = 0;
        cin >> f;
        for (int j = 1; j <= f; ++j) {
            int nf = 0;
            cin >> nf;
            t.SwitchTo(pos, nf);
            ++t.node[pos].pass;
        }
        ++t.node[pos].lasts;
    }
    for (int i = 1; i <= n; ++i) {
        int f = 0, pos = 0, ans = 0;
        cin >> f;
        bool cont = true;
        for (int i = 1; i <= f; ++i) {
            int nf = 0;
            cin >> nf;
            if (cont && t.switchTo(pos, nf)) {
                ans += t.node[pos].lasts;
            } else cont = false;
        }
        if (cont) ans = ans - t.node[pos].lasts + t.node[pos].pass;
        cout << ans << endl;
    }
    return 0;
}