Math
Редакционное расстояние и diff
Стройте таблицы редакционного расстояния для своих строк и прослеживайте оптимальное выравнивание с настраиваемой ценой замены.
Что попробовать
Введите две строки до десяти символов. Таблица Левенштейна заполняется по строкам, затем показывает оптимальное выравнивание. Вставка и удаление стоят 1; замена — 1 или 2. Расстояние −1 означает незавершённый расчёт.
Уравнения модуля
Уравнения D(i,0)=i; D(0,j)=j D(i,j)=min(D(i−1,j)+1, D(i,j−1)+1, D(i−1,j−1)+c) c=0 для равных символов; иначе стоимость замены Обратный ход даёт оптимальное выравнивание из вставок/удалений/замен
