F - Substring 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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

制約

  • S, T は 0, 1 からなる
  • 1 ≤ |T| ≤ |S| ≤ 10^6

入力

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

S
T

出力

答えを出力せよ。

入力例 1

0001
101

出力例 1

1

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

入力例 2

0101010
1010101

出力例 2

7

入力例 3

10101000010011011110
0010011111

出力例 3

1

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 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.

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