Изменения

Перейти к: навигация, поиск

Алгоритм Ландау-Вишкина (k несовпадений)

Нет изменений в размере, 18:55, 16 июня 2014
Процедура merge
'''Условие 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>.
[[Файл:algLandauVishkin6.png|380px450px]]
Вспомним, что нас интересует, совпадает ли символ текста в позиции <tex>p</tex> с соответствующими символом образца, когда <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, то есть верно ли, что <tex>y[p] = x[p-i]</tex>. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.
297
правок

Навигация