Изменения

Затем образец сканируется параллельно с текстом слева на права направо по одному символу за раз. На итерации <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>. Если <tex>i < j</tex>, в <tex>b</tex> присваивается результат работы <tex>\mathrm{merge}</tex>, которая находит количество несовпадений между <tex>x[1...j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>\mathrm{extend}</tex>, которая сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, где изменяется таблица текстовых несовпадений. Переменная <tex>r</tex> будет рассмотрена ниже.