297
правок
Изменения
Нет описания правки
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.
Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации <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>merge</tex>, которая находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>extend</tex>, которая сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, где изменяется таблица текстовых несовпадений. Переменная <tex>r</tex> будет рассмотрена ниже.
{| border="0"
[[Файл:algLandauVishkin4.png|thumb|250px|right| В таблицу pm по номеру несовпадения записывается соответствующий индекс верхнего образца, то есть <tex>pm[i][1] = a</tex>, <tex>pm[i][2] = b</tex>, <tex>pm[i][3] = c</tex> и т д.]]
Также в алгоритме используется двумерный массив несовпадений образца <tex>pm[1...m-1][1...2k+1]</tex>, генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично <tex>tm</tex>, то есть в <tex>i</tex>-ой строке содержатся позиции внутри <tex>x</tex> первых <tex>2k+1</tex> несовпадений между подстроками <tex>x[1...m-i]</tex> и <tex>x[i+1...m]</tex>. Таким образом, если <tex>pm[i, ][v] = s</tex>, то <tex>x[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x(1, m-i)</tex> и <tex>x(i+1, m)</tex> слева направо. Если число <tex>d</tex> несовпадений между этими строками меньше <tex>2k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны <tex>m+1</tex>, значению по умолчанию. Построение <tex>tm</tex> будет подробнее рассмотрено позднее.
Таким образом, для <tex>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>.
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
|-
| tm pm || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || x[1..m-i] || x[i+1..m]
|-
| '''1''' || 1 || 2 || 3 || 5 || 5 || tra || ram
