子串

题目描述

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

为了让 $T$ 成为 $S$ 的子串,需要改写 $S$ 中的一些字符。

至少需要改写多少个字符?

其中,子串指的是连续的子序列。例如,xxx 是 yxxxy 的子串,但不是 xxyxx 的子串。

输入格式

输入按以下格式从标准输入给出:

$S$
$T$

输出格式

输出改写 $S$ 所需的最少字符数。

样例

cabacc
abc

1

例如,把 $S$ 的第 $4$ 个字符 a 改写成 c,$S$ 的第 $2$ 到第 $4$ 个字符就与 $T$ 一致。

因为 $S$ 本身不包含 $T$ 作为子串,所以改写这 $1$ 个字符是最少的。

codeforces
atcoder

6

数据范围

• $S,T$ 长度为 $1$ 到 $1000$ 字符
• $T$ 的长度不超过 $S$ 的长度
• $S,T$ 只包含小写英文字母