4935：[USACO08DEC] Secret Message G

# [USACO08DEC] Secret Message G

题目描述

贝茜正在领导奶牛们逃跑。为了联络，奶牛们互相发送秘密信息。 信息是二进制的，共有 $M$（$1 \le M \le 50000$）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 $i$ 条二进制信息的前 $b_i$（$1 \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$）不会超过 $5 \times 10^5$。

输入格式

第 $1$ 行：两个整数 $M$ 和 $N$。 接下来 $M$ 行，其中的第 $i$ 行：一个整数 $b_i$，后跟 $b_i$ 个空格分隔的“0”和“1”，描述截取的消息 $i$。 接下来 $N$ 行，其中的第 $j$ 行：一个整数 $c_j$，后跟 $c_j$ 个空格分隔的“0”和“1”，描述暗号 $j$。

输出格式

$N$ 行，第 $i$ 行表示第 $i$ 个暗号可以匹配的消息数。

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 
3 
1 
1 
2 

提示

四条消息；五条暗号。截获的消息以 `010`、`1`、`100` 和 `110` 开头。可能的暗号以 `0`、`1`、`01`、`01001` 和 `11` 开头。 `0`：匹配 `010`: $1$ 个匹配。 `1`：匹配 `1`、`100` 和 `110`，$3$ 个匹配。 `01`：匹配 `010`，$1$ 个匹配。 `01001`：匹配 `010`，$1$ 个匹配。 `11`： 匹配 `1` 和 `110`，$2$ 个匹配。 标签: P2922|2008|USACO|进制|字典树 Trie

来源

P2922|[USACO08DEC] Secret Message G