← 返回题目列表

AtCoder · tessoku_book_cs

B20. 编辑距离

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

配点: 1000 点

問題文

文字列 S 和 按字典顺序比较 T 。 对于
您可以使用字符串 以下为 S ,输出以下 对 3 类型的操作。

操作1:S 里面的人物 1 选择一个并将其删除。
操作2:S 里面的人物 1 选择一个字符并将其更改为另一个字符。
操作3:S 将文字写在里面适当的位置。 1 插入一个。

转换字符串所需的最少操作数 你能匹配 S 该值应乘以 T 吗?

制約

  • S 中的字符数为 生成并给出 1 以上 2000 以下
  • T 中的字符数为 生成并给出 1 以上 2000 以下
  • S, T 由小写字母组成 打印第

入力

输入是按以下格式从标准输入给出的。

S
T

出力

请以整数形式输出答案。


入力例 1

tokyo
kyoto

出力例 1

4

如下 通过执行 4 操作, 你可以得到正方形tokyo 该值应乘以 kyoto 。 它将被扩展

  • 1 删除第一个字符: 它变成okyo 。
  • 1 删除第一个字符: 它变成kyo 。
  • 3 添加了 t :kyot 。
  • 4 添加了 o :kyoto 。

入力例 2

competitive
programming

出力例 2

10

入力例 3

abcdef
bdf

出力例 3

3