Изменения

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

'''int[][]''' algorithmLandauViskin(y : '''string''', x : '''string''') n = y.length m = x.length tm[0...n - m][1...k + 1] = m + 1 <font color=green> // инициализация </font> r = 0 j = 0 '''for''' i = 0 to n - m b = 0 '''if''' i < j b = merge(i, r, j) '''if''' b < k + 1 r = i extend(i, j, b) '''return''' tm

[[Файл: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>.

'''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

[[Файл:algLandauVishkin3.png|thumb|400px|right| Синие подстроки сравниваются в процедуре <tex>\mathrm{merge}</tex>.]]

Рассмотрим процедуру <tex>\mathrm{merge}</tex> подробнее. Она находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex> и устанавливает <tex>b</tex> равным найденному числу, при этом используется полученная ранее информация. Введем <tex>r</tex> {{---}} это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и <tex>y[r+1]</tex>. Текущий номер самой правой из проверенных на настоящий момент позиции текста равен <tex>r+tm[r][k+1]</tex>. Поэтому при обработки подстроки начинающейся с <tex>y[i+1]</tex>, можно учитывать информацию в <tex>r</tex>-ой строке <tex>tm</tex>, которая содержит информацию о сопоставлении образца с <tex>y[i]</tex>. Подходящими значениями из таблицы несовпадений являются, таким образом, <tex>tm[r][q ... k+1]</tex>, где <tex>q</tex> {{---}} это наименьшее из целых чисел, для которых <tex>r+tm[r][q] > i</tex>. Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, который был выровнен с <tex>y[r+1]</tex>, в то время как текущая позиция образца выровнена с <tex>y[i+1]</tex> {{---}} разница в <tex>i - r</tex> мест.

Таким образом, для <tex>\mathrm{merge}</tex> интерес представляет строка <tex>i - r</tex> таблицы несовпадений образца, причем используются значения <tex>pm[i-r][1...t]</tex>, где <tex>t</tex> {{---}} самое правое несовпадение в <tex>pm[i-r][1...2k+1]</tex>, такое, что <tex>pm[i-r][t] < j-i+1</tex>, так как требуются только несовпадения в подстроке <tex>x[1...j-i]</tex>.

Чтобы использовать упомянутую информацию в процедуре <tex>\mathrm{merge}</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 < p < j</tex>. Рассмотрим следующие условия для позиции <tex>p</tex>:

Возвращаемся к процедуре <tex>\mathrm{merge}</tex>. В ''случае 2'', или если в ''случае 3'' выявлено несовпадение символов, необходимо увеличить количество несовпадений символов <tex>b</tex> на единицу и обновить <tex>tm[i][b]</tex>. Соответствующими значениями таблицы для <tex>\mathrm{merge}</tex> являются <tex>tm[i-r][1...t]</tex> и <tex>tm[r][q...k+1]</tex>. Переменные <tex>u</tex> и <tex>v</tex> в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.

* Bспомним, что самая правая из интересующих нас позиций в <tex>\mathrm{merge}</tex>, а именно, <tex>j</tex>, равна <tex>r+tm[r][k+1]</tex>, если <tex>v = k+2</tex>, поэтому <tex>tm[r][k+1]</tex> будет уже использовано для предыдущего значения <tex>v</tex>, а именно, <tex>v = k+1</tex>, и поэтому позиция <tex>j</tex> должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.

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

'''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>\mathrm{merge}</tex> и <tex>\mathrm{extend}</tex>, каждая из <tex>n-m+1</tex> итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время <tex>O(n)</tex>. Общее число операций, выполняемых процедурой <tex>\mathrm{extend}</tex> во время вызовов равно <tex>O(n)</tex>, так как она проверяет каждый символ текста не больше одного раза. Процедура <tex>\mathrm{merge}</tex> при каждом вызове обрабатывает массив <tex>pm[i-r][1...2k+1]</tex> и <tex>tm[r][1...k+1]</tex>, которые в сумме имеют <tex>3k+2</tex> элементов. Время работы <tex>\mathrm{merge}</tex> можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное <tex>O(k)</tex>. Таким образом, можно видеть, что общее время анализа текста составляет <tex>O(nk)</tex>.

Рассмотрим построение <tex>pm</tex>. Используя аргументы, аналогичные применявшимся при проверке корректности процедуры <tex>\mathrm{merge}</tex>, можно показать, что для нахождения требуемого количества несовпадений на стадии <tex>s</tex> требуется <tex>\min\{2^{\log(m)-s}4k+1, m-2^{s}\}</tex> позиций, для которых выполняется ''условие B'', и в особом случае, а именно, на стадии <tex>\log m</tex>, требуется <tex>4k + 1</tex> таких позиций.

На каждой стадии <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]