Math
Редакційна відстань
Обчисліть таблицю Левенштейна й оптимальне вирівнювання рядків.
Що спробувати
Редагуйте два рядки довжиною до десяти символів. Таблиця Левенштейна заповнюється рядок за рядком, потім будує оптимальне вирівнювання. Вставки та видалення коштують 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 для однакових символів; інакше вартість заміни Зворотний прохід дає оптимальне вирівнювання вставка/видалення/заміна
