Problem
Given a text string. You can perform the following operations with it:
1. Replace one character of a string with another character.
2. Delete one arbitrary character.
3. Insert an arbitrary character at an arbitrary position in the string.
For example, using the first operation from the string "JUICE" you can get the string "SUK", using the second operation - the string "OK", using the third operation - the string "STOCK.
The minimum number of such operations that can be used to get another from one string is called the editing cost or the Levenshtein distance.
Find the Levenshtein distance for the two given strings.
Input
The program receives two strings as input, the length of each of which does not exceed 1000 characters, the strings consist only of uppercase latin letters.
Output
Required to output a single number – Levenshtein distance for given strings.
| Input |
Output |
|
ABCDEFGH
ACDEXGIH
|
3 |