B - 子字符串

得分：$200$分

问题描述

给定两个字符串$S$和$T$。

我们改变$S$中的一些字符，使得$T$成为$S$的子字符串。

至少需要改变多少个字符？

这里，子字符串是一个连续的子序列。例如，xxx是yxxxy的子字符串，但不是xxyxx的子字符串。

约束

• $S$和$T$的长度分别至少为$1$，最大为$1000$
• $T$的长度不超过$S$的长度
• $S$和$T$由小写英文字母构成

输入

输入以以下格式从标准输入中给出：

$S$

$T$

输出

打印需要改变的$S$中的最少字符数。

cabacc
abc

1

例如，将$S$中的第四个字符a改为c将会使$S$的第二个到第四个字符与$T$相匹配。

由于$S$本身没有$T$作为其子字符串，因此这一改变数量——一个字符——是必需的最少数量。

codeforces
atcoder

6