297
правок
Изменения
→Алгоритм
==Алгоритм==
[[Файл:algLandauVishkin1.png|thumb|380px|right| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.]]
При анализе текста используется двумерный массив <tex>tm[0...n-m][1...k+1]</tex>, содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его <tex>i</tex>-й строке содержатся позиции в <tex>x</tex> первых <tex>k+1</tex> несовпадений между строками <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>. Таким образом, если <tex>tm[i][v] = s</tex>, то <tex>y[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>, считая слева направо. Если число <tex>d</tex> несовпадений <tex>x[1...m]</tex> с подстрокой <tex>y[i+1...i+m]</tex> меньше <tex>k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны значению по умолчанию <tex>m+1</tex>.
Заметим, если <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>//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>r</tex> будет рассмотренна ниже.
|}
[[Файл:algLandauVishkin2.png|thumb|380px|right| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.]] Рассмотрим процедуру <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+m]</tex> с не больше чем <tex>k</tex> несовпадениями, иначе то есть найдено вхождение образца в подстроке , начинающееся с <tex>y[i+1...i+m]</tex>.
==Пример==
