Изменения
→Алгоритм Вагнера — Фишера
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с <tex>1</tex>):
<code>
'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2, '''int[]''' S2InsertCost, '''int[]''' S1DeleteCost, '''int[]''' ReplaceCost): D[0][0] = 0 '''fo'''r j = 1 '''to''' N D[0][j] = D[0][j - 1] + S2InsertCost[j] //S2InsertCost[j] - цена вставки символа S2[j] '''for''' i = 1 '''to''' M D[i][0] = D[i - 1][0] + S1DeleteCost[i] //S1DeleteCost[i] - цена удаления символа S1[i] '''for''' j = 1 '''to''' N '''if''' S1[i] != S2[j] D[i][j] = min(D[i - 1][j] + цена удаления символа S1S1DeleteCost[i], D[i][j - 1] + цена вставки символа S2S2InsertCost[j], D[i - 1][j - 1] + ReplaceCost[i][j]) //ReplaceCost[i][j] -цена замены символа S1[i] на символ S2[j]) '''else''' D[i][j] = D[i - 1][j - 1] '''return''' D[M][N]
</code>
