← 返回题目列表

Codeforces · 156/A

A. 留言

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

Moriarty 博士即将向 Sherlock Holmes 发送消息。他有一个字符串 s。

如果可以从字符串 s 中的某个位置开始读取字符串 p,则该字符串 p 被称为字符串 s 的子字符串。例如,字符串“aba”有六个子字符串:“a”、“b”、“a”、“ab”、“ba”、“aba”。

Moriarty 博士计划取出字符串 s 并从中删除一些子字符串,我们将其称为 t。那么他需要将子串t改变零次或多次。结果,他应该获得一个固定的字符串u(这是应该发送给福尔摩斯的字符串)。一项更改定义为进行以下操作之一:

- 在字符串的任意末尾插入一个字母。
- 从字符串的任意末尾删除一个字母。
- 将一个字母更改为任何其他字母。

Moriarty 非常聪明,在他选择某个子串 t 后,他总是进行最少次数的改变来获得 u。

帮助 Moriarty 从字符串 s 的所有子串中选择最佳子串 t。子字符串 t 应该最小化 Moriarty 从中获取字符串 u 所需进行的更改次数。

输入

第一行包含一个非空字符串 s,由小写拉丁字母组成。第二行包含一个非空字符串 u,由小写拉丁字母组成。两个字符串的长度都在 1 到 2000 的范围内(包含 1 和 2000)。

输出

打印唯一的整数 - Moriarty 博士必须对您选择的字符串进行的最小更改次数。

示例

输入 #1

aaaaa
aaa

输出 #1

0

输入 #2

abcabc
bcd

输出 #2

1

输入 #3

abcdef
klmnopq

输出 #3

7

注意

在第一个示例中,Moriarty 可以采用长度为 3 的任何子字符串,并且它将等于所需的消息 u,因此 Moriarty 无需进行任何更改。

在第二个示例中,您应该采用由第二个到第四个(“bca”)或第五个到第六个(“bc”)字符组成的子字符串。然后您只需进行一项更改:更改或添加最后一个字符。

在第三个示例中,初始字符串 s 不包含消息应包含的任何字符,因此,无论您选择什么字符串,都必须进行至少 7 次更改才能获得所需的消息。