[USACO08DEC] Secret Message G
二进制 Trie 同时记录终止数量和子树数量，统计两串中较短者为公共前缀的消息数。
OJ: luogu
题目 ID: P2922
难度:普及+/提高
标签:Trie前缀计数python
日期: 2026-07-16 19:57
题意
对每条暗号，统计有多少消息与它从第一位开始相同，直到两者中较短的一条结束。
思路
把所有消息插入二进制 Trie。每个节点记录：
terminal_count：恰好在此结束的消息数；subtree_count：经过此节点的消息数。
查询暗号时，沿路径每下降一层前，把当前节点终止的消息加入答案，它们是暗号的前缀。若暗号整条路径存在，最后再加当前节点的子树数，它们以暗号为前缀。两部分不会重复。
Python 知识
- 只有 0/1 两条边，使用
child_zero、child_one两个array("i")比节点字典更紧凑。 - 下标
0统一表示不存在的儿子。 - 查询位先读成列表，即使 Trie 提前失配，也已经正确消耗本行输入。
for ... else的else只在循环没有break时执行，正好处理“暗号完整走完”。
代码
python
import sys
from array import array
data = iter(map(int, sys.stdin.buffer.read().split()))
message_count, query_count = next(data), next(data)
child_zero = array("i", [0])
child_one = array("i", [0])
subtree_count = array("i", [0])
terminal_count = array("i", [0])
for _ in range(message_count):
node = 0
for _ in range(next(data)):
children = child_one if next(data) else child_zero
if not children[node]:
children[node] = len(child_zero)
child_zero.append(0)
child_one.append(0)
subtree_count.append(0)
terminal_count.append(0)
node = children[node]
subtree_count[node] += 1
terminal_count[node] += 1
answers = []
for _ in range(query_count):
bits = [next(data) for _ in range(next(data))]
node = answer = 0
for bit in bits:
answer += terminal_count[node]
node = (child_one if bit else child_zero)[node]
if not node:
break
else:
answer += subtree_count[node]
answers.append(str(answer))
print("\n".join(answers))cpp
/**
* 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-08-02
* update_at: 2026-08-02
*/
/* P2922 [USACO08DEC] Secret Message G */
/* 把消息插入 Trie，暗号匹配 = 暗号是消息的前缀 或 消息是暗号的前缀。 */
/* 答案 = 暗号路径上所有节点的 end 之和 + 最终节点的 pass - 最终节点的 end（暗号自身被重复计数）。 */
#include <bits/stdc++.h>
using namespace std;
// 字典树 Trie 模板（来自 rbook 文章 trie）：
// 节点维护 pass(经过次数) 和 end(单词结尾次数)
// 本题字符集为 {0, 1}，所以 ALPHA=2，OFFSET='0'
template <int ALPHA = 26, char OFFSET = 'a'>
struct Trie {
struct Node {
array<int, ALPHA> ch{}; // ch[c] 子节点编号，0 为空（根也是 0）
int pass = 0; // 经过该节点的字符串个数
int end = 0; // 以该节点结尾的完整字符串个数
};
vector<Node> tree; // tree[0] 为根
Trie() { tree.push_back(Node()); }
// 插入 s
void insert(const string &s) {
int u = 0;
tree[u].pass++;
for (char cc : s) {
int c = cc - OFFSET;
if (tree[u].ch[c] == 0) { // 无子节点则新建
tree[u].ch[c] = (int)tree.size();
tree.push_back(Node());
}
u = tree[u].ch[c];
tree[u].pass++;
}
tree[u].end++;
}
};
int m, n; // m 条消息，n 条暗号
Trie<2, '0'> trie; // 01 字典树，存放所有消息
// 查询暗号 s 能匹配多少条消息：
// 匹配条件 = 一个是另一个的前缀（前缀长度取较小者）。
int query(const string &s) {
int u = 0;
int ans = 0; // 路径上节点 end 的累加：这些消息是暗号 s 的前缀（含 s 本身）
for (char cc : s) {
int c = cc - '0';
u = trie.tree[u].ch[c];
if (u == 0) return ans; // 暗号走不到底：之后的节点不存在，
// 已累加的 end 就是全部匹配（消息是暗号的前缀）
ans += trie.tree[u].end;
}
// 暗号完整存在于 Trie 中：
// 还要加上"经过最终节点的消息数"（暗号是消息的前缀），
// 但等于暗号本身的消息在 pass 和 end 中各计了一次，需要减去 end。
return ans + trie.tree[u].pass - trie.tree[u].end;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
for (int i = 1; i <= m; ++i) {
int b;
cin >> b;
string s;
for (int j = 1; j <= b; ++j) {
int bit;
cin >> bit;
s.push_back('0' + bit);
}
trie.insert(s);
}
for (int i = 1; i <= n; ++i) {
int c;
cin >> c;
string s;
for (int j = 1; j <= c; ++j) {
int bit;
cin >> bit;
s.push_back('0' + bit);
}
cout << query(s) << '\n';
}
return 0;
}复杂度
时间和空间均为所有消息与暗号总位数的
总结
这类“较短串必须是较长串前缀”的计数，需要同时统计路径上的终止串和终点下方的更长串。