74
правки
Изменения
Нет описания правки
Тогда если на очередной итерации внутреннего цикла положить: <tex>i1 = sd[T[j]],\ j1 = DB</tex>, то
<tex>D(i, j) = min(A, D(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1)) (*)</tex> , где
<tex>A = \left\{\begin{array}{llcl}
</tex>
Доказательства требует лишь утверждение <tex>(*)</tex>, так как остальные формулы обосновываются так же, как и в доказательстве [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|алгоритма Вагнера {{---}} Фишера]]. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:
*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.
Псевдокод алгоритма:
