Изменения

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

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

'''if''' <tex>\langle</tex>l, p<tex>\rangle</tex> = l1 <tex>\geqslant</tex> l2 l = ? <tex>\langle</tex>l1 p = , p1 '''else''' len = <tex>\rangle</tex> : <tex>\langle</tex>l2 p = , p2<tex>\rangle</tex>

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

'''int''' i = <tex>\max</tex>(l, memPrefix) + 1 '''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] <tex>=</tex> text[pos + i]

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

'''int''' j = l

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

Двусторонний алгоритм отчасти похож на алгоритм Бойера-Мура (просмотр символов справа налево и сдвиг позиции при несовпадении на втором этапе), и в лучшем случае работает немногим медленнее его, а в худшем {{---}} значительно превосходит<ref>[http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf Journal of the Association for Computing Machinery, Vol. 38, No, 1, July 1991] Оценки скорости работы</ref>, но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура {{---}} константное количество затрачиваемой дополнительной памяти. Именно этот алгоритм (при выполнении ряда условий) используется в реализации поиска подстроки в glibc<ref>[https://github.com/bminor/glibc/blob/glibc-2.28/string/strstr.c#L88 Реализация функции strstr в glibc]</ref>.