← 返回题目列表

AtCoder · abc177_b

B. 子字符串

中文机器翻译题面 查看原题

分数: 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