配点 : $600$ 点

問題文

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

制約

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

入力

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

$S$

$T$

出力

答えを出力せよ。

0001
101

1

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

0101010
1010101

7

10101000010011011110
0010011111

1