Задача B. Расстояние Левенштейна

Автор:unknown   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.

Даны два слова. Необходимо вычислить расстояние Левенштейна между ними.

Формат входного файла

Во входном файле содержится два слова, каждое в своей строке.

Формат выходного файла

В выходном файле должно содержаться единственное число — расстояние между словами.

Ограничения

Слова состоят из малых латинских букв. Длина слов от 1 до 10000 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
aaaa
bbbb
4
2
abc
aabb
2

0.067s 0.012s 13