297
правок
Изменения
→merge
Таким образом, для <tex>merge</tex> интерес представляет строка <tex>i - r</tex> таблицы несовпадений, причем используются значения <tex>pm[i-r][1...t]</tex>, где <tex>t</tex> – самое правое несовпадение в <tex>pm[i-r][1...2k+1]</tex>, такое, что <tex>pm[i-r][t] < j-i+1</tex>, так как требуются только несовпадения в подстроке <tex>x[1...j-i]</tex>.
Чтобы использовать упомянутую информацию в процедуре <tex>merge</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 < p < j</tex>. Рассмотрим следующие условия для позиции <tex>p</tex>:
Условие <tex>A</tex>:
Условие <tex>B</tex>:
==Пример==
