Изменения

'''Двусторонний алгоритм''' (англ. ''Two Way algorithm'') — алгоритм [[Наивный алгоритм поиска Поиск подстроки в строке#Постановка задачи|поиска подстроки в строке]].

* требует Требует упорядоченный алфавит,* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти,* этап поиска за время <math>O(n)</math>* в худшем случае производится , где <tex>m<math/tex>2n {{-- m-}} длина образца, а <tex>n</mathtex> сравнений символов{{---}} длина текста.

Образец Строка <tex>x</tex> разбивается на две части <math>x_lu</math> и <math>x_rv</math> так, что <math>x=</math> <math>x_l</math> <math>x_ruv</math>. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов <math>x_rv</math> слева направо, и затем, если на этом первом этапе не происходит несовпадений, в сравнении символов <math>x_lu</math> справа налево (второй этап).Фаза предобработки, таким образом, заключается в поиске подходящего разбиения <mathtex>(u, v)</tex>.{{Определение|definition = <tex>(u, v)</tex> {{---}} '''разбиение''' строки <tex>x_lx</mathtex> , если <mathtex>x_rx = uv</mathtex>.}} 

# <math>w</math> {{---}} суффикс <math>u</math> или <math>u</math> {{---}} суффикс <math>w</math>;.# <math>w</math> {{---}} префикс <math>v</math> или <math>v</math> {{---}} префикс <math>w</math>.}}

Иными словами, <math>w</math> встречается по обе стороны границы между <math>u</math> и <math>v</math> и может "залезать" (overflow). {{Определение|definition = Длина повторения в <math>(u, v)</math> называется '''локальным периодом'''; наименьший локальный период записывается как <math>r(u, v)</math>.

Каждое разбиение <math>x</math> на <math>(u, v)</math> имеет как минимум одно повторение. Очевидно, что <math>1 \ge leqslant r(u, v) \ge leqslant |x|</math>}} {{Определение|definition = Разбиение <math>x </math> на <math>(u, v)</math> такое, что <math>r(u, v) = per(x)</math> называется '''критическим разбиением''' <math>x</math>.

Если <math>(u, v)</math> {{---}} критическое разбиение <math>x</math>, то на позиции <math>|u|</math> в <math>x</math> общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение <math>(x_lu, x_rv)</math> такое, что <math>|x_lu| < per(x)</math> и длина <math>|x_lu|</math> минимальна.Чтобы найти критическое разбиение <math>(x_lu, x_rv)</math> мы сперва вычислим <math>z</math> {{---}} максимальный суффикс <math>x</math> в лексикографическом порядке , характерном для заданного алфавита <math><=\leqslant</math> и максимальный суффикс <math>\widetilde{z~}</math> для обратного лексикографического порядка <math><=~\geqslant</math>. Затем <math>(x_lu, x_rv)</math> выбираются так, что <math>|x_lu| = \max{(|z|, |\widetilde{z~}|})</math>.Фаза предобработки может быть выполнена за время O(m) и константное количество памяти.Фаза поиска в двустороннем алгоритме состоит из сравнения символов <math>x_rv</math> слева направо и символов <math>x_lu</math> справа налево. Когда происходит несовпадение при просмотре <math>k</math>-го символа в <math>x_rv</math>, производится сдвиг длиной <math>k</math>. Когда происходит несовпадение при просмотре <math>x_lu</math>, или когда образец встретился в строке, производится сдвиг длиной <math>per(x)</math>.