Изменения

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

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

'''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> memPrefixtext.length pos <texfont color=green>\rightarrow</tex> occurences pos <tex>\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> npattern.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> 0memPrefix occurences.pushBack(pos <tex>\rightarrow</tex> occurences) pos <tex>\leftarrow</tex> = pos <tex>+</tex> qp memPrefix = pattern.length - 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>.