59
правок
Изменения
→Описание алгоритма
}}
Введем обозначение: пусть <tex>t[i]</tex> {{---}} длина наибольшего бордера для <tex>x[0 .. i - 1]</tex> за которым следует символ <tex>c \neq x[i]</tex> и <tex>-1</tex> если нет такого помеченного бордера, где <tex>0 < i \le m</tex> (<tex>t[0] = -1</tex>). Затем, после сдвига, сравнение можно продолжить между символами <tex>x[t[i]]</tex> и <tex>y[i + j]</tex> не потеряв никакого вхождения <tex>x</tex> в <tex>y</tex> и избежав отступа по тексту (смотри рисрисунок ниже). 1) [[Файл:Apostolico-Crochemore-Shifts.png]]
Пусть теперь <tex>l {{=}} 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x {{=}} a ^ l bu</tex>, где <tex>a</tex> и <tex>b \in \Sigma</tex>, а <tex>u \in \Sigma^*</tex> и <tex>a \neq b</tex>). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: <tex>l, l + 1, \ldots , m - 2, m - 1, 0, 1, \ldots , l - 1</tex>.
