B - Substring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

2 つの文字列 S, T が与えられます。

T が S の部分文字列となるように、S のいくつかの文字を書き換えます。

少なくとも何文字書き換える必要がありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • S,T は 1 文字以上 1000 文字以下
  • T の長さは S の長さ以下
  • S,T は 英小文字のみを含む

入力

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

S
T

出力

S を書き換える文字数の最小値を出力せよ。

入力例 1

cabacc
abc

出力例 1

1

例えば S の 4 文字目の a を c に書き換えることで、S の 2～4 文字目が T と一致します。

S 自身は T を部分文字列に持たないので、この 1 文字を書き換えるのが最小です。

入力例 2

codeforces
atcoder

出力例 2

6

Score : 200 points

Problem Statement

Given are two strings S and T.

Let us change some of the characters in S so that T will be a substring of S.

At least how many characters do we need to change?

Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy, but not a substring of xxyxx.

Constraints

  • The lengths of S and T are each at least 1 and at most 1000.
  • The length of T is at most that of S.
  • S and T consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

Print the minimum number of characters in S that need to be changed.

Sample Input 1

cabacc
abc

Sample Output 1

1

For example, changing the fourth character a in S to c will match the second through fourth characters in S to T.

Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.

Sample Input 2

codeforces
atcoder

Sample Output 2

6