U28039.二进制串
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
给您两个二进制字符串 a 和 b 。二进制字符串是由字符 0 和 1 组成的字符串。
您的任务是确定最大可能的数字 k,使得长度为 k 的字符串 a 的前缀是字符串 b 的子序列。
如果 a 可以从 b 中删除几个(可能是零个或全部)元素,那么序列 a 就是序列 b 的子序列。
输入格式
第一行包含两个整数 n 和 m(1≤n,m≤2∗105) - 分别是字符串 a 的长度和字符串 b 的长度。
第二行包含长度为 n 的二进制字符串 a 。
第三行包含长度为 m 的二进制字符串 b。
输出格式
输出一个数字 - 最大值 k ,使得 a 的前 k 个字符构成 b 的子序列。
输入输出样例
输入#1
5 4 10011 1110
输出#1
2
输入#2
3 5 100 11010
输出#2
3
输入#3
3 1 100 0
输出#3
0
说明/提示
样例解释 1:
字符串 10 是 1110 的子序列,但字符串 100 不是。因此答案是 2 。
样例解释 2:
a=100, b=11010,整个字符串 a 是字符串 b 的子序列,所以答案为 3。
样例解释 3:
字符串 b 不包含 1,所以答案是 0 。