101965: [AtCoder]ABC196 F - Substring 2
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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?
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.
Constraints
- Each of $S$ and $T$ consists of
0and1. - $1 ≤ |T| ≤ |S| ≤ 10^6$
Input
Input is given from Standard Input in the following format:
$S$ $T$
Output
Print the answer.
Sample Input 1
0001 101
Sample Output 1
1
Changing $T$ to 001 makes it match the $2$-nd through $4$-th characters of $S$.
Sample Input 2
0101010 1010101
Sample Output 2
7
Sample Input 3
10101000010011011110 0010011111
Sample Output 3
1