Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Расстояние Дамерау-Левенштейна

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

Ввод Вывод
XABCDE
ACBYDF
4
Источник: http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=113104#


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: