297
правок
Изменения
→Процедура merge
==Процедура merge==
[[Файл:algLandauVishkin3.png|thumb|380px400px|right| Синие подстроки сравниваются в процедуре merge. Красным отмечены несовпадения.]]
Рассмотрим процедуру <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> мест.
[[Файл:algLandauVishkin4.png|thumb|300px250px|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>p</tex> с соответствующими символом образца, когда <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, то есть верно ли, что <tex>y[p] = x[p-i]</tex>. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.
'''Случай 1. : !A and !B:''' То есть, <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] = x[p-i]</tex>. Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.
'''Случай 2. : (A and !B) or (!A and B):''' В любом случае <tex>y[p] \neq x[p-i]</tex> (если лишь условие <tex>A</tex> истинно, то <tex>y[p] \neq x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] \neq x[p-i]</tex>, с другой стороны, если выполнено только условие <tex>B</tex>, то <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] \neq x[p-i]</tex>, и опять, <tex>y[p] \neq x[p-i]</tex>). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.
'''Случай 3. : A and B:''' В этом случае мы ничего не можем сказать о том, совпадают ли символы <tex>y[p]</tex> и <tex>x[p-i]</tex>, поэтому их надо сравнить.
Возвращаемся к процедуре merge. В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов <tex>b</tex> на единицу и обновить <tex>tm[i][b]</tex>. Соответствующими значениями таблицы для <tex>merge</tex> являются <tex>tm[i-r][1...t]</tex> и <tex>tm[r][q...k+1]</tex>. Переменные <tex>u</tex> и <tex>v</tex> в начале устанавливаются равными индексам первых элементов этих двух массовов, соответственно, и последовательно увеличиваются.
tm[i][b] = pm[i - r][u]
u++
else // Случай 3 (?//todo)
I + PM[I - R, U] = R + TM[R, V]
if x[ pm[i-r][u] ] != y[ i+pm[i-r][u] ]
