1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Файл:algLandauVishkin2.png|thumb|380px|right| Синие подстроки сравниваются в процедуре <tex>\mathrm{extend}</tex>. <tex>w < k + 1</tex>]]
Рассмотрим процедуру <tex>\mathrm{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>.
{| border="0"
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
|-
| tm || '''1''' || '''2''' || '''3''' || x[1..<tex>\ldots</tex> m] || y[i+1..<tex>\ldots</tex> i+m]
|-
| '''0''' || 2 || 3 || 4 || '''t'''ram || '''t'''het
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
|-
| pm || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || x[1..<tex>\ldots</tex> m-i] || x[i+1..<tex>\ldots</tex> m]
|-
| '''1''' || 1 || 2 || 3 || 5 || 5 || tra || ram
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Нечёткий поиск]]
