pm[i, c+1] = pm[i, c+2] = … = pm[i, 2k+1] = m+1

Таким образом, для merge интерес представляет строка i - r таблицы несовпадений, причем используются значения pm[i-r, 1…t], где t – самое правое несовпадение в pm[i-r, 1…2k+1], такое, что pm[i-r, t] < j-i+1, так как требуются только несовпадения в подстроке x(1, j-i).

Чтобы понять, как упомянутая информация может использоваться в процедуре merge, рассмотрим в тексте позицию p, находящуюся в соответствующем диапазоне, i+1 < p < j. Позиция p может удовлетворять или не удовлетворять любому из приведенных ниже условий.

A: когда символы x₁ и y_r+1 совмещены, позиция p в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть y_p =/=x_p-r, и это несовпадение номер v, где q < v < k+1, то есть p - r = tm[r, v].

B: для двух копий образца, со сдвигом относительно друг друга i - r, совмещенных с текстом так, что их начальные символы лежат, соответственно, над y_r+1 и y_i+1, позиция p соответствует несовпадению между двумя шаблонами, то есть x_p-r =/=x_p-i. Это u-е несовпадение при этом сдвиге, где 1 < u < t, то есть p-i = pm[i-r, u].

Вспомним, что нас интересует, совпадает ли символ текста в позиции p с соответствующими символом образца, когда x₁ совмещен с y_i+1, то есть верно ли, что y_p = x_p-i. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.

Случай 1: не выполняется ни условие A, ни условие B. То есть, y_p = x_p-r и x_p-r = x_p-i, откуда y_p = x_p-i. Нет необходимости сравнивать символ текста с символом шаблона, так как ясно, что в этой позиции они совпадают.

Случай 2: выполняется только одно из условий, то есть либо условие A, либо условие B, но не оба сразу. В любом случае y_p =/=x_p-i. Если лишь условие A истинно, то y_p =/=x_p-r и x_p-r = x_p-i, откуда y_p =/=x_p-i. С другой стороны, если выполнено только условие B, то y_p = x_p-r и x_p-r =/=x_p-i, и опять, y_p =/=x_p-i. Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом шаблона, так как известно, что они не совпадают.

Случай 3: выполняются оба условия – и условие A, и условие B. В этом случае мы ничего не можем сказать о том, совпадают ли символы y_p и x_p-i, поэтому их надо сравнить.

В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов b на единицу и обновить tm[i, b] в процедуре merge.

Теперь опишем процедуру merge, представленную на рисунке 27. Как упоминалось ранее, соответствующими значениями таблицы для merge являются tm[i-r, 1…t] и tm[r, q…k+1]. Переменные u и v в начале устанавливаются равными индексам первых элементов этих двух векторов, соответственно, и последовательно увеличиваются соответственно векторным компонентам.

Условия окончания работы процедуры следующие. Во первых, если b = k+1, то для случая, когда шаблон расположен относительно текста так, что x₁ совмещен с y_i+1, обнаружено k+1 несовпадение, поэтому из процедуры можно выйти. Во вторых, вспомним, что самая правая из интересующих нас позиций в merge, а именно, j, равна r+tm[r, k+1], если v = k+2, поэтому tm[r, k+1] будет уже использовано для предыдущего значения v, а именно, v = k+1, и поэтому позиция j должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры. Наконец, процедуру можно прервать, если i+pm[i-r, u] > j и tm[r, v] = m+1. Если выполняется вторая часть этого условия, то r+tm[r, v] равняется j, и соответствует суммам для последующих значений v вплоть до k+1. В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста j фактически пропущена.

Остается показать, что число позиций несовпадений в таблице несовпадений шаблона достаточно для того, чтобы merge нашла все, или, если их больше k+1, первые k+1 несовпадений для y(i+1, j). Это можно показать следующим образом. Условие A выполняется не больше чем для k+1 позиции текста в диапазоне [i+1, j]. Условие B выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка i-r в таблице несовпадений шаблона, tm[i-r, 1 ... 2k+1], содержит не больше чем 2k+1 позиций несовпадений между двумя копиями шаблона, с соответствующим сдвигом i-r. Если pm[i-r, 2k+1] > j - i, то таблица содержит все позиции несовпадения шаблона самим с собой, у которых условие B выполняется для позиций текста в интервале [i+1, j]. С другой стороны, если pm[i-r, 2k+1] < j-i, то таблица может дать 2k+1 позиций текста в диапазоне [i+1, j-1], для которых выполняется условие B. Поскольку j = r+tm[r, k+1], в диапазоне [i+1, j-1] имеется до k позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть k позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере k+1 позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения шаблона относительно текста имеется не меньше k+1 несовпадений между текстом и шаблоном.

Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур merge и extend, каждая из n-m+1 итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время O(n). Общее число операций, выполняемых процедурой extend во время вызовов равно O(n), так как она проверяет каждый символ текста не больше одного раза. Процедура merge при каждом вызове обрабатывает вектора pm[i-r, 1 ... 2k+1] и tm[r, 1…k+1], которые в сумме имеют 3k+2 элементов. Время работы merge можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное O(k). Таким образом, можно видеть, что общее время анализа текста составляет O(nk).

merge(i, r, j, b)

   u = 1

   v = q

   while (b < K + 1) AND (V < K + 2)

                     AND (I + PM[I - R, U] < j or tm[r, v] =/=m + 1)

      if i + pm[i - r, u] > r + tm[r, v]

         - Случай 2, условие A

         b = b + 1

         tm[i, b] = tm[r, v] - (i - r)

         v = v + 1

      else if i + pm[i - r, u] < R + TM[R, V]

         - СЛУЧАЙ 2, УСЛОВИЕ B

         B = B + 1

         TM[I, B] = PM[I - R, U]

         U = U + 1

      else

         - I + PM[I - R, U] = R + TM[R, V]

         - СЛУЧАЙ 3

         IF Xpm[i-r,u] =/=yi+pm[i-r,u]

            b = b + 1

            tm[i, b] = pm[i - r, u]

         u = u +1

         v = v + 1

- инициализация

 

r = 2l-1

j = 2l-1

- вычисление строк pm в множестве l

for i = 2l-1 to 2l - 1

   b = 0

   if i < J

      merge(I, R, J, B)

      IF 

         r = i

         extend(i, j, b)

Теперь осталось только обратиться к вычислению таблицы несовпадений шаблона на стадии предварительных вычислений. Не теряя общности, можно предположить, что m является некоторой степенью 2. В алгоритме предварительной обработки используется разбиение множества {1, 2, ... , m-1} из m-1 строк pm на следующие log₂m подмножеств: