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).
Пусть теперь <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>.
# <tex>i = m</tex>:
#: Если <tex> k < l </tex> и <tex>x[k] {{=}} y[j + k]</tex>, тогда следующая тройка <tex>(i, j, k + 1)</tex>.
#: Иначе либо <tex>k < l</tex> и <tex>x[k] \ne y[l + k]</tex>, либо <tex>k = l</tex>. Если <tex>k = l</tex>, то вхождение x в y найдено. В обоих случаях следующая тройка вычисляется , как в случае <tex>l < i < m </tex>.
===Псевдокод===
==Асимптотика алгоритма==
Стадия предподсчета, а именно вычисление массива <tex>t</tex> и переменной <tex>l</tex> занимает <math>O(m)</math> времени и константное количество памяти. Этап поиска занимает <math>O(n)</math> времени , более того , алгоритм в худшем случае выполнит <tex>\frac{3}{2} n</tex> сравнений.
==См. также==
