English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Levenstein Distance

A text string is given. You can perform the following operations with it:

1. Replace one character of the string with another character.

2. Delete one arbitrary character.

3. Insert an arbitrary character in an arbitrary place of 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 "DRAIN.

The minimum number of such operations by which one can get another from one line is called the editing cost or the Levenshtein distance.

Determine the Levenshtein distance for two given rows.

Input data

The program receives two lines for input, each of which does not exceed 1000 characters in length, the lines consist only of uppercase Latin letters.

Output data

It is required to output one number – the Levenshtein distance for these rows.

Examples
Input data
ABCDEFGH
ACDEXGIH
Output data
3

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)