UOJ Logo

NOI.AC

1S 512MB

#1737. 无间道

统计

题目描述

小明是一个被派遣到美国的间谍,这一天神盾局开始调查起了小明的身份,于是布置给小明一道题目来检测他是否是间谍。由于这是一道性命攸关的大事,所以小明找来了机智的你,希望你能帮他逃脱险境。

神盾局给定小明一个字符串,小明可以对这个字符串进行插入一个字符,删除一个字符,替换一个字符。进而转换成小明心中的字符串,小明需要讲最少进行的插入\删除\替换的操作数告诉神盾局才能证明他不是间谍。

输入说明

第一行输入一行字符串表示神盾局给小明的字符串$s1$.

第二行输入一行字符串表示小明心中的字符串$s2$ .

输出说明

输出小明最少需要操作的次数

Example

输入:

abcd
dd

输出:

3

数据规模

对于$50\%$ 的数据 $s1, s2$的长度均小于等于$20$;

对于$100\%$的数据, $s1, s2$ 的长度均小于等于$1000$;