Edit Distance

Time limit8sMemory limit128 MB

Summary

Given strings A and B up to length 17000, find the minimum number of insert, delete, and substitute operations to turn A into B.

Level: Medium7 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

Consider an edit script that turns string $A$ into string $B$ . An edit script is made of the four commands below, and each command consumes $A$ from the front while building the result string.

Add (a): output one character to the result. $A$ is left untouched.
Delete (d): remove the first character of $A$ and output nothing.
Modify (m): remove the first character of $A$ and output a different character instead.
Copy (c): remove the first character of $A$ and output that same character.

Copy is free. The length of an edit script is the number of add, delete, and modify commands it uses, and the shortest edit script is the one that minimizes the count of these three commands.

Given two strings $A$ and $B$ , find the minimum number of add, delete, and modify commands (the edit distance) used by a shortest edit script that turns $A$ into $B$ .

Input

The first line contains string $A$ and the second line contains string $B$ . Both strings consist only of English letters (uppercase and lowercase) and digits, and each has length between $1$ and $17000$ , inclusive.

Output

Print a single integer: the minimum number of add, delete, and modify commands needed to turn $A$ into $B$ .

Examples4

Example 1
Input
```
abcde
xabzdey
```
Expected output
```
3
```
Example 2
Input
```
a
a
```
Expected output
```
0
```
Example 3
Input
```
a
b
```
Expected output
```
1
```
Example 4
Input
```
kitten
sitting
```
Expected output
```
3
```