3014 - 前缀匹配-东方博宜OJ

题目描述

小 $A$ 有 $M$ 个由数字 01 构成的二进制数组，小 $B$ 有 $N$ 个由数字 01 构成的二进制数组。

请问小 $B$ 的每个二进制数组可以和小 $A$ 的多少个二进制数组完成前缀匹配。

这里前缀匹配的含义是：如果小 $B$ 的第 $i$ 个二进制数组是小 $A$ 的第 $j$ 个二进制数组的前缀，或者小 $A$ 的第 $j$ 个二进制数组是小 $B$ 的第 $i$ 个二进制数组的前缀，都可以称为这两个二进制数组完成了前缀匹配。

输入

第 $1$ 行读入两个整数 $M,N$ 。

接下来 $M$ 行，每行先读入一个整数 $X_i$ ，表示小 $A$ 的二进制数组的长度，再读入 $X_i$ 个由数字 $0$ 或 $1$ 构成的数组。

接下来 $N$ 行，每行先读入一个整数 $Y_i$ ，表示小 $B$ 的二进制数组的长度，再读入 $Y_i$ 个由数字 $0$ 或 $1$ 构成的数组。

输出

输出 $N$ 行，第 $i$ 行输出的是小 $B$ 的第 $i$ 个二进制数组可以和小 $A$ 的二进制数组完成匹配的数组数量。

样例

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

5 5
4 1 0 1 0
3 0 0 0
2 1 0
1 1
2 0 1
5 1 1 1 1 1
5 1 0 1 0 1
1 1
1 0
2 1 1

说明

小 $B$ 有 $5$ 个二进制数组。

他的第 $1$ 个数组，可以匹配小 $A$ 的第 $1$ 个数组。

他的第 $2$ 个数组，可以匹配小 $A$ 的第 $2,3,4$ 个数组。

他的第 $3$ 个数组，可以匹配小 $A$ 的第 $1$ 个数组。

他的第 $4$ 个数组，可以匹配小 $A$ 的第 $1$ 个数组。

他的第 $5$ 个数组，可以匹配小 $A$ 的第 $2,4$ 个数组。

对于 $10\%$ 的数据，满足 $1 \le M,N \le 10$ ， $1 \le X_i,Y_i \le 10$ ， $\sum X_i + \sum Y_i \le 30$ 。

对于 $100\%$ 的数据，满足 $1 \le M,N \le 50000$ ， $1 \le X_i,Y_i \le 10000$ ， $\sum X_i + \sum Y_i \le 500000$ 。

来源

东方博宜OJ

标签

题目参数

上一题下一题