297
правок
Изменения
→merge
Чтобы использовать упомянутую информацию в процедуре <tex>merge</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 < p < j</tex>. Рассмотрим следующие условия для позиции <tex>p</tex>:
[[Файл:algLandauVishkin5.png|thumb|380px|right| ..Условие A]]
'''Условие 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]]
'''Условие 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>.
Вспомним, что нас интересует, совпадает ли символ текста в позиции <tex>p</tex> с соответствующими символом образца, когда <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, то есть верно ли, что <tex>y[p] = x[p-i]</tex>. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.
<tex>!A and !B</tex>: То есть, <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] = x[p-i]</tex>. Нет необходимости сравнивать символ текста с символом шаблона, так как ясно, что в этой позиции они совпадают.
<tex>(A and !B) or (!A and B)</tex>: В любом случае <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>). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом шаблона, так как известно, что они не совпадают.
==Пример==
