题目描述

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

你的任务是确定最大的整数 $k$，使得字符串 $a$ 的长度为 $k$ 的前缀是字符串 $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$ 的一个子序列。

说明/提示

在第一个样例中，字符串 '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$。

由 ChatGPT 4.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

2
2
1
1
3
0