← 返回题目列表

Codeforces · 1968/B

B. 优先级

中文机器翻译题面 查看原题

给定两个二进制字符串 $$$a$$$ 和 $$$b$$$。二进制字符串是由字符“0”和“1”组成的字符串。

你的任务是确定最大可能的数字 $$$k$$$,使得长度为 $$$k$$$ 的字符串 $$$a$$$ 的前缀是字符串 $$$b$$$ 的子序列。

如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。

输入

第一行由一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) 组成 - 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n,m \le 2 \cdot 10^5$$$) - 分别是字符串 $$$a$$$ 的长度和字符串 $$$b$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$a$$$。

每个测试用例的第三行包含一个长度为$$$m$$$的二进制字符串$$$b$$$。

保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。同样,所有测试用例的值 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个数字 - 最大 $$$k$$$,使得 $$$a$$$ 的前 $$$k$$$ 字符形成 $$$b$$$ 的子序列。

示例

输入 #1

6
5 4
10011
1110
3 3
100
110
1 3
1
111
4 4
1011
1111
3 5
100
11010
3 1
100
0

输出 #1

2
2
1
1
3
0

注意

在第一个示例中,字符串 '$$$10$$$' 是 '$$$1\color{red}11\color{red}0$$$' 的子序列,但字符串 '$$$100$$$' 不是。所以答案是$$$2$$$。

在第五个示例中,$$$a$$$='$$$100$$$',$$$b$$$='$$$1\color{red}{10}1\color{red}0$$$',整个字符串$$$a$$$是字符串$$$b$$$的子序列。所以答案是$$$3$$$。

在第六个示例中,字符串 $$$b$$$ 不包含“$$$1$$$”,因此答案为 $$$0$$$。