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