Алгоритм Апостолико-Крочемора — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Алгоритм Апостолико-Крочемора''' (англ. ''Apostolico-Crochemore algorithm'') - вариация [[Алгоритм Бойера-...»)
 
Строка 1: Строка 1:
 
'''Алгоритм Апостолико-Крочемора''' (англ. ''Apostolico-Crochemore algorithm'') - вариация [[Алгоритм Бойера-Мура|Алгоритма Бойера-Мура]].
 
'''Алгоритм Апостолико-Крочемора''' (англ. ''Apostolico-Crochemore algorithm'') - вариация [[Алгоритм Бойера-Мура|Алгоритма Бойера-Мура]].
 +
 +
==Характерные черты==
 +
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти,
 +
* этап поиска занимает <math>O(n)</math> времени,
 +
* выполняет <tex>\frac{3}{2} n</tex> сравнений в худшем случае.

Версия 14:34, 3 марта 2016

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

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

  • этап предобработки занимает [math]O(m)[/math] времени и константное количество памяти,
  • этап поиска занимает [math]O(n)[/math] времени,
  • выполняет [math]\frac{3}{2} n[/math] сравнений в худшем случае.