9743: ABC196 —— F - Substring 2
[Creator : ]
Description
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?
What is a substring? $T$ is said to be a substring of $S$ when some contiguous part of $S$ matches $T$. For example, `000` is a substring of `10001`, while `11` is not.
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?
What is a substring? $T$ is said to be a substring of $S$ when some contiguous part of $S$ matches $T$. For example, `000` is a substring of `10001`, while `11` is not.
Input
Input is given from Standard Input in the following format:
```
$S$
$T$
```
```
$S$
$T$
```
Output
Print the answer.
Constraints
- Each of $S$ and $T$ consists of `0` and `1`.
- $1 ≤ |T| ≤ |S| ≤ 10^6$
- $1 ≤ |T| ≤ |S| ≤ 10^6$
Sample 1 Input
0001
101
Sample 1 Output
1
Changing T to 001 makes it match the 2-nd through 4-th characters of S.
Sample 2 Input
0101010
1010101
Sample 2 Output
7
Sample 3 Input
10101000010011011110
0010011111
Sample 3 Output
1