Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).
При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.
Определите расстояние Дамерау-Левенштейна для двух данных строк.
Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
Выходные данные
Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
XABCDE
ACBYDF
|
4 |