#1590. [Usaco2008 Dec]Secret Message 秘密信息

[Usaco2008 Dec]Secret Message 秘密信息

题目描述

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

信息是二进制的,共有 mm 条。反间谍能力很强的约翰已经部分拦截了这些信息,知道了第 ii 条二进制信息的前 bib_i 位。他同时知道,奶牛使用 nn 条密码。但是,他仅仅了解第 jj 条密码的前 cjc_j 位。

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

输入格式

  • 第一行: 两个数:n,mn,m
  • 接下来 nn 行:每行先输入一个整数表示信息的长度,之后输入这个信息。所有数字之间都用空格隔开。
  • 接下来 mm 行:每行先输入一个整数表示密码的长度,之后输入这个密码。所有数字之间都用空格隔开。

输出格式

mm 行,每行分别输出每条密码的匹配信息数。

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

数据规模与约定

对于 100%100\% 的数据,1m500001\le m \le 50000,1n500001\le n \le 50000,1bi100001 \le b_i \le 10000,1cj100001\le c_j \le 10000

在输入文件中,位的总数(即i=1nbi+i=1nci\sum^{n}_{i=1} b_i+ \sum^{n}_{i=1} c_i)不会超过 5×1055\times 10^5

提示

输入提示

共有 44 条信息,55 条密码。

被截获的信息以 010010,11,100100110110 开头。

可能的密码以 00,11,0101,01001010011111 开头。

输出提示

00 仅和 010010 匹配,共匹配 11 次;1111,100100110110 匹配,共匹配 33 次;0101 仅和 010010 匹配,共匹配 11 次;0100101001 仅和 010010 匹配,共匹配 11 次;111111110110 匹配,共匹配 22 次。

题目来源

Usaco 2008 Dec Gold