Изменения
→Алгоритм Вагнера — Фишера
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с <tex>1</tex>):
<code>
D([0,][0) ] = 0 для всех '''fo'''r j от = 1 до '''to''' N D([0,][j) ] = D([0,][j-1) ] + цена вставки символа S2[j] для всех '''for''' i от = 1 до '''to''' M D([i,][0) ] = D([i-1,][0) ] + цена удаления символа S1[i] для всех '''for''' j от = 1 до '''to''' N если '''if''' S1[i] != S2[j] то D([i,][j) ] = min( D([i-1, ][j) ] + цена удаления символа S1[i], D([i, ][j-1) ] + цена вставки символа S2[j], D([i-1, ][j-1) ] + цена замены символа S1[i] на символ S2[j]) )'''else''' иначе D([i, ][j) ] = D([i-1, ][j-1)] вернуть '''return''' D([M,][N)]
</code>
Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления <tex>D(i, j)</tex> не нужны также <tex>D(i-1,0)</tex> <tex>\dots</tex> <tex>D(i-1,j-1)</tex>. Поэтому алгоритм можно переписать как
<code>
</code>
