Алгоритм Апостолико-Крочемора

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Алгоритм Апостолико-Крочемора (англ. Apostolico-Crochemore algorithm) - вариация Алгоритма Бойера-Мура.

Характерные черты

  • этап предобработки занимает [math]O(m)[/math] времени и константное количество памяти,
  • этап поиска занимает [math]O(n)[/math] времени,
  • выполняет [math]\frac{3}{2} n[/math] сравнений в худшем случае.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Апостолико-Крочемора&oldid=52363»