74
правки
Изменения
м
Нет описания правки
'''for''' j '''from''' 1 '''to''' n
''// Стоимость замены''
'''if''' S[i] == T[j] '''then''' cost replaceCost = 0 '''else''' cost replaceCost = 1
d[i, j] = minimum(
'''for''' i '''from''' 0 '''to''' m
'''for''' j '''from''' 0 '''to''' n
вычислить D(i+ 1, j+ 1); '''return''' D(m+ 1, n+ 1);
Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
'''else'''
D[i + 1, j + 1] = minimum(D[i, j], D[i + 1, j], D[i, j + 1]) + 1
D[i + 1, j + 1] = minimum(D[i + 1, j + 1], D[i1+ 1, j1+ 1] + (i - i1 - 1) + 1 + (j - j1 - 1))
sd[S[i]] = i
