2422 - 编辑距离

题目描述

AB2 个字符串。要用最少的字符操作将字符串 A 转换为字符串 B。这里所说的字符操作包括:

(1) 删除 A 一个字符;

(2) 在 A 中插入一个字符;

(3) 将 A 一个字符改为另一个字符。

将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 AB 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的 2 个字符串 AB,计算出它们的编辑距离 d(A,B)

输入

第一行是字符串 A,第二行是字符串 B

字符串AB都不含空格,字符串长度 ≤ 1800。

输出

将编辑距离 d(A,B) 输出。

样例

输入

fxpimu
xwrs

输出

5
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题