子串匹配

题目描述

给定由 0, 1 组成的字符串 $S, T$。

通过改写 $T$ 中的一些字符,使 $T$ 成为 $S$ 的子串。

至少需要改写多少个字符?

什么是子串?

取出 $S$ 的某个连续部分得到的字符串与 $T$ 一致时,称 $T$ 是 $S$ 的子串。 例如,000 是 10001 的子串,但 11 不是 10001 的子串。

输入格式

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

$S$
$T$

输出格式

输出答案。

样例

0001
101

1

将 $T$ 改写为 001 后,$S$ 的第 $2$ 到第 $4$ 个字符与 $T$ 一致。

0101010
1010101

7

10101000010011011110
0010011111

1

数据范围

• $S, T$ 由 0, 1 组成
• $1 \le |T| \le |S| \le 10^6$