#1590. [Usaco2008 Dec]Secret Message 秘密信息
[Usaco2008 Dec]Secret Message 秘密信息
题目描述
贝茜正在领导奶牛们逃跑。为了联络,奶牛们互相发送秘密信息。
信息是二进制的,共有 条。反间谍能力很强的约翰已经部分拦截了这些信息,知道了第 条二进制信息的前 位。他同时知道,奶牛使用 条密码。但是,他仅仅了解第 条密码的前 位。
对于每条密码 ,他想知道有多少截得的信息能够和它匹配。也就是说,有多少信息和这条密码有着相同的前缀。当然,这个前缀长度必须等于密码和那条信息长度的较小者。
输入格式
- 第一行: 两个数:
- 接下来 行:每行先输入一个整数表示信息的长度,之后输入这个信息。所有数字之间都用空格隔开。
- 接下来 行:每行先输入一个整数表示密码的长度,之后输入这个密码。所有数字之间都用空格隔开。
输出格式
共 行,每行分别输出每条密码的匹配信息数。
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
数据规模与约定
对于 的数据,,,,。
在输入文件中,位的总数(即)不会超过 。
提示
输入提示
共有 条信息, 条密码。
被截获的信息以 ,, 和 开头。
可能的密码以 ,,, 和 开头。
输出提示
仅和 匹配,共匹配 次; 和 , 和 匹配,共匹配 次; 仅和 匹配,共匹配 次; 仅和 匹配,共匹配 次; 和 和 匹配,共匹配 次。
题目来源
Usaco 2008 Dec Gold