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