形式化题目

给定两个二进制串集合：

• 信息集合 $X = \{x_1, x_2, \dots, x_N\}$，$x_i$ 长度为 $b_i$；
• 密码集合 $Y = \{y_1, y_2, \dots, y_M\}$，$y_j$ 长度为 $c_j$。

对每条密码 $y_j$，求下标 $i$ 的个数，使得 $x_i$ 与 $y_j$ 的前 $\min(|x_i|, |y_j|)$ 位完全相同。

等价刻画：设 $|x_i| \leqslant |y_j|$，比较长度就是 $|x_i|$，条件即 $x_i = y_j[0:|x_i|]$，也就是"$x_i$ 是 $y_j$ 的前缀"；$|y_j| \leqslant |x_i|$ 的情形完全对称。因此

也就是说，题目要求的全部是比较"谁是谁的前缀"。

样例

4 条信息 $\{010,\ 1,\ 100,\ 110\}$，5 条密码 $\{0,\ 1,\ 01,\ 01001,\ 11\}$， 逐条密码按上面的等价刻画核对：

注意第 5 行：密码 $11$ 与信息 $1$ 比较时较短者是信息、与信息 $110$ 比较时较短者是 密码，两个方向都要统计；而 $01001$ 虽然更长，也只与 $010$ 的前 3 位相同，答案仍为 1。

正解

思路

朴素做法与瓶颈

最直接的做法是对每条密码遍历全部 $N$ 条信息逐位比较。当 $N = M = 5 \times 10^4$ 时， 比较对数达到 $2.5 \times 10^9$，显然超时。更本质的问题是这些比较互相不共享： 每条密码都从头与每条信息比一遍，大量比较其实反复核对了相同的前缀——所有以 1 开头的信息，在和每一条以 1 开头的密码比较时都重做了第一位。

把两两比较改写成前缀归属查询

等价刻画告诉我们，匹配只有"信息是密码前缀"和"密码是信息前缀"两种情形。于是不再 逐对比较，而是把全部信息组织成一棵 01-Trie（字典树）：相同前缀自动共享成同一条 路径，一条信息就是树上从根出发的一条路径。每个节点维护两个计数：

• through[v]：路径经过 $v$ 的信息条数（恰好终止在 $v$ 的也算经过）；
• end[v]：恰好终止在 $v$ 的信息条数。

插入信息 $x_i$ 时，沿路每进入一个节点 through += 1，到达终点再 end += 1； 重复出现的信息按条数累加，不会丢。

查询：沿途终止数 + 终点剩余经过数

查询密码 $y$ 时，沿树逐位走，答案由两部分组成：

1. 比密码短、且是密码前缀的信息：它们的终点恰好落在 $y$ 的查询路径上， 等于路径上各节点 end 之和；
2. 比密码长、以密码为前缀的信息：它们的路径经过 $y$ 的终点 $v$ 但不在 $v$ 终止， 等于 through[v] - end[v]（经过 $v$ 的 = 终止在 $v$ 的 + 继续往下的）。

若中途走不动（孩子不存在），说明更深处不再有任何信息，第 2 类不存在，答案就只是 沿途的 end 之和。两部分的分界处理保证不重不漏：与密码完全相等的信息既是 “密码前缀"也是"信息前缀”，它的 end[v] 在沿途被计入一次、在最后又被 through - end 减掉一次，恰好只算一条。

下图是样例信息建出的 Trie，括号内为每个节点的 end（终止数）与 through（经过数）：

flowchart LR
    R["根"] -->|"0"| A["0 (end 0, through 1)"]
    A -->|"1"| B["01 (end 0, through 1)"]
    B -->|"0"| C["010 (end 1, through 1)"]
    R -->|"1"| D["1 (end 1, through 3)"]
    D -->|"0"| E["10 (end 0, through 1)"]
    E -->|"0"| F["100 (end 1, through 1)"]
    D -->|"1"| G["11 (end 0, through 1)"]
    G -->|"0"| H["110 (end 1, through 1)"]

以密码 11 为例：先走到节点 1，沿途累计 end = 1（信息 1 恰好终止于此，属于 第 1 类）；再走到终点 11，补上 through - end = 1 - 0 = 1（信息 110 属于第 2 类）， 合计 2，正是样例答案。节点 1 的 through = 3 则解释了密码 1 的答案 3：信息 1、100、110 全部经过它。

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:10
# update_at: 2026-09-30 13:10

import sys

ONE = b'1'  # 按空白切分后，位 1 的字节串形态；与它比较把每个位映射成孩子下标 0/1

# 01-Trie 用三个平行列表存节点，编号从 0（根）开始：
# ch[v][t] 是节点 v 沿位 t 的孩子编号（0 表示不存在），end[v] 是恰好终止在 v 的信息条数，
# through[v] 是路径经过 v 的信息条数（终止在 v 的也算经过）。
Trie = tuple[list[list[int]], list[int], list[int]]


def build_trie(messages: list[list[bytes]]) -> Trie:
    """把全部截获信息依次插入 01-Trie，统计每个节点的终止数与经过数。"""
    ch: list[list[int]] = [[0, 0]]
    end: list[int] = [0]
    through: list[int] = [0]
    for bits in messages:
        v = 0
        for t in bits:
            t = t == ONE                      # 位即孩子下标：b'0'→0，b'1'→1
            if not ch[v][t]:                  # 孩子不存在则新建节点
                ch.append([0, 0])
                end.append(0)
                through.append(0)
                ch[v][t] = len(ch) - 1
            v = ch[v][t]
            through[v] += 1
        end[v] += 1
    return ch, end, through


def match_count(bits: list[bytes], trie: Trie) -> int:
    """统计能与这条密码匹配的信息条数：重合前缀长恰好等于 min(密码长, 信息长)。"""
    ch, end, through = trie
    v = 0
    ans = 0
    for t in bits:
        v = ch[v][t == ONE]
        if not v:                             # 这一位无路可走：更深处不可能再有信息，
            return ans                        # 能匹配的只有路径上恰好终止的那些
        ans += end[v]
    return ans + through[v] - end[v]          # 密码走完：补上比密码更长、经过终点的信息


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))
    messages: list[list[bytes]] = []
    for _ in range(n):
        msg_len = int(next(data))              # 题面的 b_i
        messages.append([next(data) for _ in range(msg_len)])

    trie = build_trie(messages)
    out: list[str] = []
    for _ in range(m):
        code_len = int(next(data))             # 题面的 c_j
        out.append(str(match_count([next(data) for _ in range(code_len)], trie)))
    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:22
 * update_at: 2026-10-05 03:22
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXNODE = 500005; // 节点总数不超过信息位总数 5*10^5，再加根

typedef long long ll;

// 01-Trie：ch[v][t] 是节点 v 的 t 孩子（t=0/1），0 同时表示"不存在"和根
int ch[MAXNODE][2];
int through_cnt[MAXNODE]; // through_cnt[v]：路径经过 v 的信息条数（终止在 v 的也算经过）
int end_cnt[MAXNODE];     // end_cnt[v]：恰好终止在 v 的信息条数
int node_cnt = 0;         // 已用节点数，根是 0

int pwd[MAXNODE]; // 当前密码的每一位，先整行读入再走树，断路也不用担心输入残留

// 把一条信息插入 Trie：沿路每个节点 through+1，终点 end+1
void trie_insert(ll len) {
    int v = 0; // 从根出发
    for (ll i = 1; i <= len; i++) {
        int t;
        cin >> t;
        if (ch[v][t] == 0) {
            node_cnt++;
            ch[v][t] = node_cnt;
        }
        v = ch[v][t];
        through_cnt[v]++;
    }
    end_cnt[v]++;
}

// 查询一条密码：沿途累加 end（比密码短、是密码前缀的信息），
// 全部走通再补 through-end（比密码长、以密码为前缀的信息）
ll trie_query(ll len) {
    ll ans = 0;
    int v = 0;
    for (ll i = 1; i <= len; i++) {
        int t = pwd[i];
        if (ch[v][t] == 0) {
            // 断路：更深处没有任何信息，第 2 类不存在
            return ans;
        }
        v = ch[v][t];
        ans += end_cnt[v];
    }
    // 与密码完全相等的信息在沿途已被计入一次，
    // through-end 恰好把它减掉，不会重复统计
    ans += through_cnt[v] - end_cnt[v];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        ll len;
        cin >> len;
        trie_insert(len);
    }
    for (ll j = 1; j <= m; j++) {
        ll len;
        cin >> len;
        for (ll k = 1; k <= len; k++) cin >> pwd[k];
        cout << trie_query(len) << "\n";
    }
    return 0;
}

build_trie() 用三个平行列表 ch、end、through 存树（ch[v][t] 为孩子编号， 0 兼作"不存在"与根），match_count() 实现上面的两部分计数：ONE = b'1' 把字节 b'1' 布尔化直接当孩子下标（b'0' → 0，b'1' → 1），走不动时 return ans 返回沿途 end 之和，全部走通则 return ans + through[v] - end[v]。

复杂度

• 时间：建树 $O(\sum b_i)$，查询每条密码至多走自己的长度、断路即停，共 $O(\sum c_j)$，合计 $O(\sum b_i + \sum c_j)$。由 $\sum b_i + \sum c_j \leqslant 500000$， 总步数不超过 $5 \times 10^5$，与 $N \cdot M$ 无关，线性读入与输出同阶。
• 空间：节点数不超过信息产生的不同前缀数加根，即 $O(\sum b_i) \leqslant 5 \times 10^5$， 每节点存 2 个孩子下标与 2 个计数。真实数据本地实测峰值约 44 MB、单组约 0.06 s， 低于 128 MB 内存限制（本地验证 13 组数据全部输出一致）。

总结

匹配条件等价于"一条串是另一条的前缀"，因此把全部信息插入 01-Trie、让公共前缀共享， 并让每个节点同时记录"经过数"与"终止数"。查询密码时沿路径累加沿途终止数（比密码短的 匹配者），走通后补上终点的"经过数减终止数"（比密码长的匹配者），两部分恰好不重不漏。 一次建树加每条密码一次树上行走，把 $O(N \cdot M)$ 的两两前缀比较压缩到 $O(\sum b_i + \sum c_j)$ 的线性复杂度。