297
правок
Изменения
→Процедура merge
Вспомним, что нас интересует, совпадает ли символ текста в позиции <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> в начале устанавливаются равными индексам первых элементов этих двух массовов, соответственно, и последовательно увеличиваются.
* Процедуру можно прервать, если <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>y[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"
|align="left" colspan="4"|
<font size=2>
</font>
|}
