Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).
При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.
Определите расстояние Дамерау-Левенштейна для двух данных строк.
|
Ввод |
Вывод |
|
XABCDE
ACBYDF
|
4 |
Источник: http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=113104#