Substring

题目描述

给出两个字符串 $S$ 和 $T$。
我们可以改变 $S$ 中的一些字符，使得 $T$ 成为 $S$ 的一个子串。
至少需要改变多少个字符？
这里，子串是连续的子序列。例如，$xxx$ 是 $yxxxy$ 的子串，但不是 $xxyxx$ 的子串。

输入格式

输入按下述格式从标准输入提供：
$S$
$T$

输出格式

输出需要在 $S$ 中改变的最少字符数。

cabacc
abc

1

codeforces
atcoder

6

提示

$S$ 和 $T$ 的长度各至少为 $1$ 且最多为 $1000$。
$T$ 的长度不超过 $S$ 的长度。
$S$ 和 $T$ 由小写英文字母组成。例如，将 $S$ 的第 4 个字符 $a$ 改为 $c$ 会使 $S$ 的第 2 到第 4 个字符与 $T$ 匹配。
由于 $S$ 本身不包含 $T$ 作为子串，这个改变次数——1——是所需的最少值。

标签: AtCoder|abc177B

来源

AtCoder|abc177B