297
правок
Изменения
Нет описания правки
[[Файл:algLandauVishkin1.png|thumb|380px|right| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.]]
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.
Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации <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 \leqslant r < i</tex>. Если <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>r</tex> будет рассмотренна ниже.
{| border="0"
На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа шаблона цикл <tex>for</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} < i < 2^{s}-1)</tex>. Если не считать время работы процедур <tex>merge</tex> и <tex>extend</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>extend</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>merge</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>merge</tex> занимает время <tex>O(min\{2^{log(m)-s}4k+1, m-2^{s}\})</tex>, что равно <tex>O(2k2^{\log (m-s)})</tex>. Таким образом, общее время для стадии <tex>s</tex> равно <tex>O(m+2^{l-1}(2k2^{\log (m-s)}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета (//todo). Таким образом, общие затраты времени, включающие предварительную обработку шаблона и анализ текста, равны <tex>O(k(n + m \log m)</tex>.
Пусть <tex>x = "tram"</tex>, <tex>y = "thetrippedtrap"</tex>, <tex>k = 2</tex>.
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
