Изменения

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

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

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

Навигация