297
правок
Изменения
→Алгоритм
[[Файл:algLandauVishkin1.png|thumb|380px|right| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.]]
При анализе текста используется двумерный массив несовпадений текста <tex>tm[0...n-m][1...k+1]</tex>, содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его <tex>i</tex>-й строке содержатся позиции в <tex>x</tex> первых <tex>k+1</tex> несовпадений между строками <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>. Таким образом, если <tex>tm[i][v] = s</tex>, то <tex>y[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>, считая слева направо. Если число <tex>d</tex> несовпадений <tex>x[1...m]</tex> с подстрокой <tex>y[i+1...i+m]</tex> меньше <tex>k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны значению по умолчанию <tex>m+1</tex>.
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.
Рассмотрим процедуру <tex>merge</tex> подробнее. Она находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex> и устанавливает b равным найденному числу, при этом используется полученая ранее информация. Введем <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>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>, значению по умолчанию.
==Пример==
