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> //todo. Рассмотрим следующие условия для позиции <tex>p</tex>:
'''Условие A''': когда символы <tex>x[1]</tex> и <tex>y[r+1]</tex> совмещены, позиция <tex>p</tex> в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть <tex>y[p] \neq x[p-r]</tex>, и это несовпадение номер <tex>v</tex>, где <tex>q < v < k+1</tex>, то есть <tex>p - r = tm[r][v]</tex>.
