297
правок
Изменения
Нет описания правки
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.
//todo (рис 1)
Образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации <tex>i</tex> с образцом сравнивается подстрока <tex>y[i+1...i+m]</tex>. <tex>j</tex> - обозначим самую правую позицию в тексте, достигнутую за предыдущие итерации, то есть <tex>j</tex> является максимальным из чисел <tex>r+tm[r, k + 1]</tex>, где <tex>0 <= r < i</tex>//todo. Если <tex>i < j</tex>, в <tex>b</tex> присваивается результат работы <tex>merge</tex>, которая находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>extend</tex>, которая сравнивает пары символов из подстрок <tex>y[j + 1...i + m]<tex> и <tex>x[j - i + 1...m]<tex>, и в случае несовпадения <tex>b</tex> увеличивается и таблица текстовых несовпадений обновляется. Если найдено <tex>k+1</tex> несовпадений, обработка заканчивается, иначе найдено вхождение образца, начинающегося с <tex>y[i+1]</tex>.
==Пример==
Пусть <tex>x = "tram"</tex>, <tex>y = "thetrippedtrap"</tex>, <tex>k = 2</tex>.
[[Файл:algorithm-landau-vishkin-tm.jpg|450px|thumb|center|'''dfdftm // todo''', dfdf.]]//todo pm
