Расстоянием Левенштейна между двумя строками s и t называется количество атомарных изменений, с помощью которых можно одну строку превратить в другую. Под атомарными изменениями подразумеваются: удаление одного символа, вставка одного символа, замена одного символа на другой.
Найдите расстояние Левенштейна для предложенной пары строк.
В первой строке дана строка s, во второй — строка t. Длины обеих строк не превосходят 1000. Строки состоят из маленьких латинских букв.
Выведите единственное число — расстояние между строками.
|
abacaba abaabc |
2 |
|
innokentiy innnokkentia |
3 |
|
r x |
1 |