1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Асимптотика==
{{Утверждение|statement= Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита.
|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]]<ref>В этом конспекте приведена реализация за <tex>O(n^2)</tex> и неконстантную память, реализацию за <tex>O(n)</tex> и константную память можно посмотреть вот [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 тут] </ref>, поэтому рассмотрим только стадию поиска.}}
{{Утверждение|statement= Фаза поиска требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} длина строки, в которой выполняется поиск.
}}
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
==Примечания==
<references />
==Источники информации==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
