297
правок
Изменения
→merge
Чтобы использовать упомянутую информацию в процедуре <tex>merge</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 < p < j</tex>. Рассмотрим следующие условия для позиции <tex>p</tex>:
[[Файл:algLandauVishkin5.png|thumb|380px|right| ..]]
'''Условие A''': когда символы <tex>x[1]</tex> и <tex>y[r+1]</tex> совмещены, позиция <tex>p</tex> в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть <tex>y[p] \neq x[p-r]</tex>, и это несовпадение номер <tex>v</tex>, где <tex>q < v < k+1</tex>, то есть <tex>p - r = tm[r][v]</tex>.
[[Файл:algLandauVishkin6.png|thumb|380px|right| ..]] '''Условие B''': для двух копий образца, со сдвигом относительно друг друга <tex>i - r</tex>, совмещенных с текстом так, что их начальные символы лежат, соответственно, над <tex>y[r+1]</tex> и <tex>y[i+1]</tex>, позиция <tex>p</tex> соответствует несовпадению между двумя шаблонами, то есть <tex>x[p-r] \neq x[p-i]</tex>. Это <tex>u</tex>-е несовпадение при этом сдвиге, где <tex>1 < u < t</tex>, то есть <tex>p-i</tex> = <tex>pm[i-r][u]</tex>.
==Пример==
