Изменения
→Ценность алгоритма
==Характерные черты==
* требует Требует упорядоченный алфавит,
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти,
* этап поиска за время <math>O(n)</math>, где <tex>m </tex> {{---}} длина образца, а <tex>n </tex> {{---}} длина текста.
==Описание алгоритма==
==Псевдокод==
'''function''' twoWaySearch('''String ''' pattern, '''String ''' text):'''vector<int>'''
<font color=green>//предобработка <tex>-</tex> вычисление критической позиции (в которой строка делится на <tex>u</tex> и <tex>v</tex>)</font>
<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>
<font color=green>//<tex>p</tex> <tex>-</tex> период <tex>x</tex>, <tex>l</tex> <tex>-</tex> такая критическая позиция, что <tex>l<p</tex></font>
'''vector<int> ''' occurences <font color= <texgreen>\varnothing// набор всех вхождений образца в текст</texfont> '''int''' pos <tex>\leftarrow</tex> = 0 '''int''' memPrefix <tex>\leftarrow</tex> = 0
'''while''' pos + pattern.length <tex>\leqslant</tex> text.length
<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]
i++
'''if''' i <tex>\leqslant</tex> pattern.length
pos <tex>\leftarrow</tex> = pos + <tex>\max</tex>(i <tex>-</tex> l, memPrefix <tex>-</tex> p <tex>+</tex> 1) memPrefix <tex>\leftarrow</tex> = 0
'''else'''
<font color=green>//второй этап: просмотр <tex>u</tex> справа налево</font>
'''int''' j <tex>\leftarrow</tex> = l
'''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]
j--
'''if''' j <tex>\leqslant</tex> memPrefix
occurences.pushBack(pos <tex>\rightarrow</tex> occurences) pos <tex>\leftarrow</tex> = pos <tex>+</tex> p memPrefix <tex>\leftarrow</tex> = pattern.length <tex>-</tex> p
'''return''' occurences
== Ценность алгоритма ==
Двусторонний алгоритм отчасти похож на алгоритм Бойера-Мура (просмотр символов справа налево и сдвиг позиции при несовпадении на втором этапе), и в лучшем случае работает немногим медленнее его, а в худшем {{---}} значительно превосходит<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>, но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура {{---}} константное количество затрачиваемой дополнительной памяти.
== Примечания ==
<references/>
== См. также Источники информации ==* [[Алгоритм Кнутаhttp://monge.univ-mlv.fr/~mac/Articles-PDF/CP-Морриса1991-Пратта ]jacm.pdf Оригинал статьи (M. Crochemore, D. Perrin)]* [[Алгоритм Бойераhttp://www-igm.univ-Мура]mlv.fr/~lecroq/string/node26.html#SECTION00260 Краткое описание алгоритма, пример работы]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория:Точный поиск]]
