Изменения

Перейти к: навигация, поиск

Алгоритм Ландау-Вишкина (k несовпадений)

79 байт добавлено, 16:03, 15 июня 2014
Алгоритм
|}
[[Файл:algLandauVishkin2.png|thumb|380px|right| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.Подстроки, которые сравниваются в процедуре extend]]
Рассмотрим процедуру <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>i</tex>-ой итерации), либо не будет достигнуто <tex>y[i+m]</tex> с не больше чем <tex>k</tex> несовпадениями, то есть найдено вхождение образца, начинающееся с <tex>y[i+1]</tex>.
==Пример==
297
правок

Навигация