101771: [AtCoder]ABC177 B - Substring
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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