Изменения

Остается показать, что число позиций несовпадений в таблице несовпадений шаблона достаточно для того, чтобы <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> несовпадений между текстом и шаблоном.

==Пример==