297
правок
Изменения
→Алгоритм
{| border="0"
|align="left" colspan="4"|
<font size=32>
tm[0...n-m][1...k+1] = m+1 // инициализация
r = 0
Рассмотрим процедуру <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>.
{| border="0"
|align="left" colspan="4"|
<font size=2>
extend(i, j, b)
while (b < k + 1) and (j - i < m)
j++
if y[j] != x[j-1]
b++
tm[i][b] = j - i
</font>
|}
==Пример==
