74
правки
Изменения
Нет описания правки
*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.
Тогда если символ <tex>S[i]</tex> встречался в <tex>T</tex> на позиции <tex>j1</tex>, а символ <tex>T[j]</tex> встречался в <tex>S</tex> на позиции <tex>i1</tex>; то <tex>T</tex> может быть получена из <tex>S</tex> удалением символов <tex>S[i1 + 1]..S[i - 1]</tex>, транспозицией ставших соседними <tex>S[i1]</tex> и <tex>S[i]</tex> и вставкой символов <tex>T[j1 + 1]..T[j - 1]</tex>. Суммарно на это будет затрачено <tex>D(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1)</tex> операций. Следовательно выражение с условием <tex>(*)</tex> выбирает оптимальную последовательность операций, рассматривая случай с транспозицией и без неё.
Псевдокод алгоритма:
