分数: 200 点
问题陈述
给定两个字符串 S 和 T.
让我们改变一些字符 S 这样 T 将是以下子串 S.
我们至少需要改变多少个字符?
这里,子串是连续的子序列。例如, xxx 是一个子串 yxxxy,但不是 xxyxx.
约束
- 的长度 S 和 T 每个至少 1 最多 1000.
- 的长度 T 最多是 S.
- S 和 T 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
S T
输出
打印中的最小字符数 S 需要更改。
示例输入 1
cabacc abc
示例输出 1
1
例如更改第四个字符 a in S to c 将匹配第二个到第四个字符 S to T.
自从 S 本身没有 T 作为其子字符串,此更改数量 - 1 - 是所需的最小值。
示例输入 2
codeforces atcoder
示例输出 2
6