OI题库

【题目描述】

字符串是数据结构和计算机语言里很重要的数据类型，在计算机语言中，对于字符串我们有很多的操作定义，因此我们可以对字符串进行很多复杂的运算和操作。实际上，所有复杂的字符串操作都是由字符串的基本操作组成。例如，把子串a替换为子串b，就是用查找、删除和插入这三个基本操作实现的。因此，在复杂字符串操作的编程中，为了提高程序中字符操作的速度，我们就应该用最少的基本操作完成复杂操作。
在这里，假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a；那么，把字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。
例如，如a=“ABC”，b=“CBCD”，则a与b的编辑距离为2。
你的任务就是：编一个最快的程序来计算任意两个字符串的编辑距离。

【输入格式】

第1行为字符串a；第2行为字符串b。

【输出格式】

编辑距离。

【样例输入】

ABC
CBCD

【样例输出】

2

【提示】

注：字符串的长度不大于1000，字符串中的字符全为大写字母。

【来源】