U28039.二进制串

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给您两个二进制字符串 aabb 。二进制字符串是由字符 0011 组成的字符串。

您的任务是确定最大可能的数字 kk,使得长度为 kk 的字符串 aa 的前缀是字符串 bb 的子序列。

如果 aa 可以从 bb 中删除几个(可能是零个或全部)元素,那么序列 aa 就是序列 bb 的子序列。

输入格式

第一行包含两个整数 nnm(1n,m2105)m(1 \leq n,m \leq 2 * 10^5) - 分别是字符串 aa 的长度和字符串 bb 的长度。

第二行包含长度为 nn 的二进制字符串 aa

第三行包含长度为 mm 的二进制字符串 bb

输出格式

输出一个数字 - 最大值 kk ,使得 aa 的前 kk 个字符构成 bb 的子序列。

输入输出样例

  • 输入#1

    5 4
    10011
    1110

    输出#1

    2
  • 输入#2

    3 5
    100
    11010

    输出#2

    3
  • 输入#3

    3 1
    100
    0

    输出#3

    0

说明/提示

样例解释 11
字符串 101011101110 的子序列,但字符串 100100 不是。因此答案是 22

样例解释 22
a=100a=100b=11010b=11010,整个字符串 aa 是字符串 bb 的子序列,所以答案为 33

样例解释 33
字符串 bb 不包含 11,所以答案是 00

首页