F - Substring 2

Score : $600$ points

Problem Statement

Given are strings $S$ and $T$ consisting of 0 and 1.
We will change some of the characters in $T$ so that $T$ becomes a substring of $S$.
How many characters do we need to change at least?

Constraints

• Each of $S$ and $T$ consists of 0 and 1.
• $1 ≤ |T| ≤ |S| ≤ 10^6$

Input

Input is given from Standard Input in the following format:

$S$

$T$

Output

Print the answer.

0001
101

1

Changing $T$ to 001 makes it match the $2$-nd through $4$-th characters of $S$.

0101010
1010101

7

10101000010011011110
0010011111

1