← 返回题目列表

AtCoder · abc196_f

F. 子串 2

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

分数: 600 点

问题陈述

给出的是字符串 S 和 T 组成 0 和 1.
我们将更改其中的一些字符 T 这样 T 成为子串 S.
我们至少需要改变多少个字符?

什么是子串? T 据说是一个子串 S 当某些连续部分 S 匹配 T。 例如, 000 是一个子串 10001,同时 11 不是。

约束

  • 每个 S 和 T 包括 0 和 1.
  • 1 ≤ |T| ≤ |S| ≤ 10^6

输入

输入由标准输入按以下格式给出:

S
T

输出

打印答案。


示例输入 1

0001
101

示例输出 1

1

改变 T to 001 使其匹配 2-nd 通过 4第一个字符 S.


示例输入 2

0101010
1010101

示例输出 2

7

示例输入 3

10101000010011011110
0010011111

示例输出 3

1