59
правок
Изменения
Нет описания правки
* этап поиска занимает <math>O(n)</math> времени,
* выполняет <tex>\frac{3}{2} n</tex> сравнений в худшем случае.
==Описание алгоритма==
Нам даны: <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>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).
