74
правки
Изменения
м
sdlastPosition[S[i]] = i
Нет описания правки
Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
<tex>lastInSlastPosition[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>
<tex>last</tex> {{---}} на i-й итерации внешнего цикла индекс последнего символа <tex>T: T[last] = S[i]</tex>
Тогда если на очередной итерации внутреннего цикла положить: <tex>i' = lastInSlastPosition[T[j]],\ j' = last</tex>, то
<tex>D(i, j) = min(A, D(i', j') + (i - i' - 1) + 1 + (j - j' - 1))</tex><tex>(*)</tex>
D[0, j + 1] = INF
'''int''' lastInSlastPosition[0..количество различных символов в S и T] ''//для каждого элемента C алфавита задано значение lastInSlastPosition[C]''
'''foreach''' ('''char''' Letter '''in''' (S + T))
'''if''' Letter не содержится в sdlastPosition добавить Letter в lastInSlastPosition lastInSlastPosition[Letter] = 0
'''for''' i '''from''' 1 '''to''' M
'''int''' last = 0
'''for''' j '''from''' 1 '''to''' N
'''int''' i' = lastInSlastPosition[T[j]]
'''int''' j' = last
'''if''' S[i] == T[j] '''then'''
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[i' + 1, j' + 1] + (i - i' - 1) + 1 + (j - j' - 1))
'''return''' D[M + 1, N + 1]
