297
правок
Изменения
→Процедура merge
[[Файл:algLandauVishkin5.png|380px]]
'''Условие 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|380px]]
Вспомним, что нас интересует, совпадает ли символ текста в позиции <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>, поэтому их надо сравнить.
Условия окончания работы процедуры следующие:
* Eсли <tex>b = k+1</tex>, то для случая, когда шаблон образц расположен относительно текста так, что <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, обнаружено <tex>k+1</tex> несовпадение, поэтому из процедуры можно выйти.
* Bспомним, что самая правая из интересующих нас позиций в <tex>merge</tex>, а именно, <tex>j</tex>, равна <tex>r+tm[r][k+1]</tex>, если <tex>v = k+2</tex>, поэтому <tex>tm[r][k+1]</tex> будет уже использовано для предыдущего значения <tex>v</tex>, а именно, <tex>v = k+1</tex>, и поэтому позиция <tex>j</tex> должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.
* Процедуру можно прервать, если <tex>i+pm[i-r][u] > j</tex> и <tex>tm[r][v] = m+1</tex>. Если выполняется вторая часть этого условия, то <tex>r+tm[r][v]</tex> равняется <tex>j</tex>, и соответствует суммам для последующих значений <tex>v</tex> вплоть до <tex>k+1</tex>. В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста <tex>j</tex> фактически пропущена.
Остается показать, что число позиций несовпадений в таблице несовпадений шаблона образца достаточно для того, чтобы <tex>merge</tex> нашла все, или, если их больше <tex>k+1</tex>, первые <tex>k+1</tex> несовпадений для <tex>y[i+1...j]<tex>. Это можно показать следующим образом. Условие A выполняется не больше чем для <tex>k+1</tex> позиции текста в диапазоне <tex>y[i+1...j]</tex>. Условие B выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка <tex>i-r</tex> в таблице несовпадений шаблонаобразца, <tex>tm[i-r][1...2k+1]</tex>, содержит не больше чем <tex>2k+1</tex> позиций несовпадений между двумя копиями шаблонаобразца, с соответствующим сдвигом <tex>i-r</tex>. Если <tex>pm[i-r][2k+1] > j - i</tex>, то таблица содержит все позиции несовпадения шаблона образца самим с собой, у которых условие B выполняется для позиций текста в интервале <tex>y[i+1...j]</tex>. С другой стороны, если <tex>pm[i-r][2k+1] < j-i</tex>, то таблица может дать <tex>2k+1</tex> позиций текста в диапазоне <tex>y[i+1][j-1]</tex>, для которых выполняется условие B. Поскольку <tex>j = r+tm[r][k+1]</tex>, в диапазоне <tex>[i+1][j-1]</tex> имеется до <tex>k</tex> позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть <tex>k</tex> позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере <tex>k+1</tex> позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения шаблона образца относительно текста имеется не меньше <tex>k+1</tex> несовпадений между текстом и шаблономобразцом.
{| border="0"
