Описание

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

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

Задача: Расстояние по Левенштейну

Дана текстовая строка. С ней можно выполнять следующие операции:
 
1. Заменить один символ строки на другой символ.
 
2. Удалить один произвольный символ.
 
3. Вставить произвольный символ в произвольное место строки.
 
Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.
 
Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.
 
Определите расстояние Левенштейна для двух данных строк.
 
Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
 
Выходные данные
Требуется вывести одно число – расстояние Левенштейна для данных строк.

Ввод Вывод
ABCDEFGH
ACDEXGIH
3

Источник:  https://informatics.mccme.ru/mod/statements/view3.php?id=766&chapterid=1791# 
 


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


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

Ваш ответ:

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


Нет

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