1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Псевдокод==
'''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>\leqslant</tex>)
<tex>\langle</tex>l, p<tex>\rangle</tex> = l1 <tex>\geqslant</tex> l2 ? <tex>\langle</tex>l1, p1<tex>\rangle</tex> : <tex>\langle</tex>l2, 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= 0green>// набор всех вхождений образца в текст</font>
'''int''' pos = 0
'''int''' memPrefix = 0
j--
'''if''' j <tex>\leqslant</tex> memPrefix
occurences = .pushBack(pos )
pos = pos + p
memPrefix = pattern.length - 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>.
== См. также ==
