AT_abc177_b [ABC177B] Substring

题目描述

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

你可以将 $S$ 的若干字符进行修改，使得 $T$ 成为 $S$ 的一个子串。

你至少需要修改多少个字符？

这里，子串指的是连续的子序列。例如，xxx 是 yxxxy 的子串，但不是 xxyxx 的子串。

输入格式

输入以以下格式从标准输入读入。

$S$ $T$

输出格式

输出将 $S$ 修改为包含 $T$ 作为子串所需修改的最小字符数。

输入输出样例 #1

输入 #1

cabacc
abc

输出 #1

1

输入输出样例 #2

输入 #2

codeforces
atcoder

输出 #2

6

说明/提示

限制条件

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

样例解释 1

例如，将 $S$ 的第 $4$ 个字符 a 改为 c 后，$S$ 的第 $2$ 到第 $4$ 个字符就与 $T$ 完全一致。由于 $S$ 本身不包含 $T$ 作为子串，因此只需修改这 $1$ 个字符即可达到要求。

由 ChatGPT 4.1 翻译