题目描述

0, 1 からなる文字列 $S,\ T$ が与えられます。
$T$ が $S$ の部分文字列となるように、$T$ のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？

部分文字列とは？ $S$ のある連続した部分を取り出してできる文字列が $T$ と一致するとき、$T$ は $S$ の部分文字列であるといいます。 例えば、000 は 10001 の部分文字列ですが、11 は 10001 の部分文字列ではありません。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $T$

输出格式

答えを出力せよ。

题目大意

存在两个字符串 $S,T$,问你最少修改多少次 $T$ 才能使 $T$ 成为 $S$ 的子集？

0001
101

1

0101010
1010101

7

10101000010011011110
0010011111

1

提示

制約

• $S,\ T$ は 0, 1 からなる
• $1\ <\ = |T|\ <\ =\ |S|\ <\ =\ 10^6$

Sample Explanation 1

$T$ を 001 と書き換えると、$S$ の $2$ 文字目から $4$ 文字目が $T$ と一致します。