Изменения

* требует Требует упорядоченный алфавит,

* этап поиска за время <math>O(n)</math>, где <tex>m </tex> {{---}} длина образца, а <tex>n </tex> {{---}} длина текста.

'''function''' twoWaySearch('''String ''' pattern, '''String ''' text):'''vector<int>'''

<tex>\langle</tex>l1, p1<tex>\rangle</tex> = maxSuffix(pattern, <tex>\leftarrowleqslant</tex> ) <tex>\langle</tex>l2, p2<tex>\rangle</tex> = maxSuffix(pattern, <tex>\leqslantgeqslant</tex>) <tex>\langle</tex>l2l, p2p<tex>\rangle</tex> = l1 <tex>\leftarrowgeqslant</tex> maxSuffix(patternl2 ? <tex>\langle</tex>l1, p1<tex>\geqslantrangle</tex>) '''if''' l1 : <tex>\geqslantlangle</tex> l2 l = l1 p = p1 '''else''' len = l2 p = , p2<tex>\rangle</tex>

'''vector<int> ''' occurences <font color= <texgreen>\varnothing// набор всех вхождений образца в текст</texfont> '''int''' pos <tex>\leftarrow</tex> = 0 '''int''' memPrefix <tex>\leftarrow</tex> = 0

<font color=green>//первая фазапервый этап: просмотр <tex>v</tex> слева направо</font> '''int''' i <tex>\leftarrow \= max</tex>(l, memPrefix) + 1 '''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] <tex>=</tex> text[pos + i]

pos <tex>\leftarrow</tex> = pos + <tex>\max</tex>(i <tex>-</tex> l, memPrefix <tex>-</tex> p <tex>+</tex> 1) memPrefix <tex>\leftarrow</tex> = 0

<font color=green>//вторая фазавторой этап: просмотр <tex>u</tex> справа налево</font> '''int''' j <tex>\leftarrow</tex> = l

occurences.pushBack(pos <tex>\rightarrow</tex> occurences) pos <tex>\leftarrow</tex> = pos <tex>+</tex> p memPrefix <tex>\leftarrow</tex> = pattern.length <tex>-</tex> p

== Источники информации Ценность алгоритма ==* Двусторонний алгоритм отчасти похож на алгоритм Бойера-Мура (просмотр символов справа налево и сдвиг позиции при несовпадении на втором этапе), и в лучшем случае работает немногим медленнее его, а в худшем {{---}} значительно превосходит<ref>[http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf Оригинал статьи (MJournal of the Association for Computing Machinery, Vol. Crochemore38, DNo, 1, July 1991] Оценки скорости работы</ref>, но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура {{---}} константное количество затрачиваемой дополнительной памяти. Perrin Именно этот алгоритм (при выполнении ряда условий)]* используется в реализации поиска подстроки в glibc<ref>[httphttps://www-igmgithub.univcom/bminor/glibc/blob/glibc-mlv2.fr/~lecroq28/string/node26strstr.htmlc#SECTION00260 Краткое описание алгоритма, пример работыL88 Реализация функции strstr в glibc]</ref>.