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

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

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

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

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