← 返回题目列表

Codeforces · 530/G

G. 编辑距离

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

两个字母字符串之间的编辑距离计算为将一个字符串转换为另一个字符串的一系列编辑操作的最小总成本。允许的编辑操作是:

- 替换:用一个字母替换另一个字母的成本等于这些字母在英文字母表中的索引号之差。
- 插入/删除:将字母插入字符串或从字符串中删除字母的成本等于该字母在英文字母表中的索引号(参见示例)。

给你两个字符串。求它们之间的编辑距离。

输入

输入数据由两行组成,每行包含一串小写拉丁字母。每个字符串的长度在 1 到 100 个字母之间(含 1 和 100 个字母)。

输出

输出一个整数——字符串之间的编辑距离。

示例

输入 #1

arc
bug

输出 #1

8

输入 #2

dome
drone

输出 #2

19

注意

在第一个示例中,您应该将 a 替换为 b(成本 1),将 r 替换为 u(成本 3),将 c 替换为 g(成本 4)。

在第二个示例中,您应该插入 r(成本 18),并将 m 替换为 n(成本 1)。