Изменения

'''Двусторонний алгоритм''' (англ. ''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>.}} {{Определение|definition = Длина повторения в <math>(u, v)</math> называется '''локальным периодом'''; наименьший локальный период записывается как <math>r(u, v)</math>.

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

Каждое разбиение <math>x</math> на <math>(u, v)</math> имеет как минимум одно повторение. Очевидно, что <math>1 \leqslant r(u, v) \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>.

'''function''' twoWaySearch('''String ''' pattern, '''String ''' text):'''vector<int>''' n <font color= pattern.length green>//предобработка <tex>\langle-</tex>len1, p1вычисление критической позиции (в которой строка делится на <tex>\rangleu</tex> и <tex>\leftarrowv</tex> maxSuffix(pattern, <tex>\leqslant)</texfont>) <tex>\langle</tex>len2l1, p2p1<tex>\rangle</tex> <tex>\leftarrow</tex> = maxSuffix(pattern, <tex>\geqslantleqslant</tex>) '''if''' len1 <tex>\geqslantlangle</tex> len2: len = len1 p = p1 '''else''': len = len2 p = l2, p2 occurences = <tex>\varnothingrangle</tex> pos = maxSuffix(pattern, <tex>\leftarrowgeqslant</tex> 0) memPrefix <tex>\leftarrowlangle</tex> 0 '''if''' len < n/2 '''and''' pattern[1l, p<tex>\ldotsrangle</tex>len] = l1 <tex>-\geqslant</tex> суффикс pattern[len + 1l2 ? <tex>\ldotslangle</tex>len + p]: '''while''' pos + n l1, p1<tex>\leqslantrangle</tex> text.length: i <tex>\leftarrow \maxlangle</tex>(ll2, memPrefix) + 1 '''while''' i p2<tex>\leqslantrangle</tex> n '''and''' pattern[i] <font color=green>//<tex>=p</tex> text[pos + i]: i++ '''if''' i <tex>\leqslant-</tex> n: pos период <tex>\leftarrowx</tex> pos + , <tex>\maxl</tex>(i <tex>-</tex> lenтакая критическая позиция, memPrefix что <tex>-l</tex> p <tex>+</tex> 1) memPrefix <tex>\leftarrow</texfont> 0 '''elsevector<int> ''': j occurences <texfont color=green>\leftarrow// набор всех вхождений образца в текст</texfont> l '''whileint''' j <tex> > </tex> memPrefix pos = 0 '''andint''' pattern[j] <tex>memPrefix =</tex> text[pos + j]:0 j-- '''ifwhile''' j pos + pattern.length <tex>\leqslant</tex> memPrefix:text.length pos <tex>\rightarrow</tex> occurences pos <texfont color=green>\leftarrow</tex> pos <tex>+</tex> p memPrefix первый этап: просмотр <tex>\leftarrowv</tex> n <tex>-слева направо</texfont> p '''elseint''': q <tex>\leftarrow \i = max</tex>(lenl, n <tex>-</tex> lenmemPrefix) <tex>+</tex> 1 '''while''' pos + n i <tex>\leqslant</tex> textpattern.length: i <tex>\leftarrow</tex> len + 1 '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos <tex>+</tex> i]: i++ '''if''' i <tex>\leqslant</tex> n:pattern.length pos = pos + max(i - l, memPrefix - p + 1) memPrefix = 0 '''else''' <texfont color=green>\leftarrow</tex> pos /второй этап: просмотр <tex>+u</tex> i <tex>-справа налево</texfont> len '''elseint''': j <tex>\leftarrow</tex> len= l '''while''' j <tex> > </tex> 0 memPrefix '''and''' pattern[j] <tex>=</tex> text[pos <tex>+</tex> j]: j-- '''if''' j <tex>=\leqslant</tex> 0:memPrefix occurences.pushBack(pos <tex>\rightarrow</tex> occurences) pos <tex>\leftarrow</tex> = pos <tex>+</tex> qp memPrefix = pattern.length - p