74
правки
Изменения
Нет описания правки
memPrefix <tex>\leftarrow</tex> 0
'''while''' pos + pattern.length <tex>\leqslant</tex> text.length
<font color=green>//первая фазапервый этап: просмотр <tex>v</tex> слева направо</font>
i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
'''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] <tex>=</tex> text[pos + i]
memPrefix <tex>\leftarrow</tex> 0
'''else'''
<font color=green>//вторая фазавторой этап: просмотр <tex>u</tex> справа налево</font>
j <tex>\leftarrow</tex> l
'''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]
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>, но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура {{---}} константное количество затрачиваемой дополнительной памяти.
== Источники информации ==
* [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 Краткое описание алгоритма, пример работы]
== Примечания ==
<references/>
== См. также ==
