Изменения

Затем образец сканируется параллельно с текстом слева на права направо по одному символу за раз. На итерации <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> будет рассмотрена ниже.

Рассмотрим процедуру <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>.

'''void''' extend(i : '''int''', j : '''int''', b : '''int''') '''while''' (b < k + 1) '''and''' (j - i < m) j++ '''if''' y[j] <tex>\neq</tex> x[j-1] b++ tm[i][b] = j - i

'''if''' i + pm[i - r][u] > r + tm[r][v] <font color=green> // Случай 2, условие A </font>

'''else''' '''if''' i + pm[i - r][u] = r + tm[r][v] <font color=green> // Случай 3 </font>

'''void''' precalc pm precalcPm()

На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа образца цикл <tex>\mathrm{for}</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} \leqslant i \leqslant 2^{s}-1)</tex>. Если не считать время работы процедур <tex>\mathrm{merge}</tex> и <tex>\mathrm{extend}</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>\mathrm{extend}</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>\mathrm{merge}</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>\mathrm{merge}</tex> занимает время <tex>O(\min\{2^{\log(m)-s}4k+1, m-2^{s}\})</tex>, что равно <tex>O(2k2^{\log (m)-s})</tex>. Таким образом, общее время для стадии <tex>s</tex> равно <tex>O(m+2^{s-1}(2k2^{\log (m) -s}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета <tex>O</tex> <tex>\displaystyle \left(\sum_{i=1}^{\log m} km\right) = O(dkm km \log m)</tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.

| tm || '''1''' || '''2''' || '''3''' || x[1..<tex>\ldots</tex> m] || y[i+1..<tex>\ldots</tex> i+m]

| pm || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || x[1..<tex>\ldots</tex> m-i] || x[i+1..<tex>\ldots</tex> m]