Изменения
Нет описания правки
==Описание алгоритма==
Нам даны: <tex>y</tex> {{---}} текст, <tex>x</tex> {{---}} образец, <tex>m {{=}} |x|</tex>, <tex>n {{=}} |y|</tex>.
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с <tex>y[j \ldots j + m - 1]</tex>. Предположим, что первое несовпадение произойдет между <tex>x[i]</tex> и <tex>y[i + j]</tex> при <tex>0 < i < m</tex>. Тогда <tex>x[0 \ldots i - 1] {{=}} y[j \ldots i + j - 1] {{=}} u</tex> и <tex>a {{=}} x[i] \neq y[i + j] {{=}} b</tex>.
Когда сдвиг возможен, разумно ожидать, что префикс <tex>v</tex> шаблона совпадет c некоторым суффиксом <tex>u</tex>. Более того, если мы хотим избежать несовпадения при сдвиге, то нужно, чтобы символ, следующий за префиксом <tex>v</tex> в шаблоне, не совпадал с <tex>a</tex>. Такой наибольший префикс <tex>v</tex> называется '''помеченным бордером''' строки <tex>u</tex>.
{{Определение
|id=tagged border
|definition='''Помеченный бордер''' (англ. ''tagged border'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \forall i = 1 \ldots n - 1, \alpha[i] {{=}} \beta[i + (m - n)], \alpha[n] \neq \beta[m], n {{=}} |\alpha|, m {{=}} |\beta|</tex>.
}}
Пусть теперь <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, j, k)</tex> где:
* шаблон сравнивается с <tex>y[j, \ldots , j + m - 1]</tex>
* <tex>0 \leqslant k \leqslant l</tex> и <tex>x[0, \ldots, k - 1] {{=}} y[j, \ldots , j + k - 1]</tex>* <tex>l \leqslant i < m</tex> и <tex>x[l, \ldots, i - 1] {{=}} y[j + l, \ldots , i + j - 1]</tex>
Вначале инициализируем эту тройку <tex>(l, 0, 0)</tex>.
Теперь опишем, как по уже вычисленной тройке <tex>(i, j, k)</tex> перейти к следующей.
# <tex>i = l</tex>:
#: Если <tex>x[i] {{=}} y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.
#: Если <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex>.
# <tex>l < i < m </tex>
#: Если <tex>x[i] {{=}} y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.
#: Если <tex>x[i] \neq y[i + j]</tex>, тогда возможны два случая в зависимости от значения <tex>t[i]</tex>:
#:* Если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex>.
#:* Если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</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>, то вхождение <tex>x</tex> в <tex>y</tex> найдено. В обоих случаях следующая тройка вычисляется, как в случае <tex>l < i < m </tex>.
