5842: 字符串的相似度

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:9 Solved:1

Description

给一个源串和目标串,用最少的操作次数,使得源串进行下列操作之后等于目标串。

   1、在给定的位置插入字符

   2、将当前字符替换成任意字符

   3、删除任意字符

Input

第1行,一个只包含大小写字母和数字的字符串,表示源串,长度不超过1000。

第2行,一个只包含大小写字母和数字的字符串,表示目标串,长度不超过1000。

Output

1行,1个整数,表示将源串等于目标串的最少操作次数。

Sample Input Copy

aa
bb

Sample Output Copy

2

HINT

20%的数据,目标串的长度为1。
100%的数据,源串和目标串的长度<=1000。