@Alpendev2876

Сложность алгоритмов для определения подстроки в строке?

Как должны выглядеть разные уровни сложности алгоритмов для определения строки в другой строке в качестве подстроки?
  • Вопрос задан
  • 90 просмотров
Пригласить эксперта
Ответы на вопрос 2
gbg
@gbg
Любые ответы на любые вопросы
Они должны выглядеть как алгоритм Ахо-Корасик, который имеет линейную сложность и является наиболее оптимальными.
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
H = |haystack|, n = |needle|, a — размер алфавита.
Примитивный алгоритм: предобработки нет, работа в среднем 2H, максимум O(Hn).
Типичные быстрые алгоритмы: предобработка O(n) или O(n+a), работа в среднем <H, максимум O(Hn).
Автоматные алгоритмы: предобработка O(na) или O(n+a), работа =H.
Существуют СТРАШНЫЕ алгоритмы с работой в среднем <H и максимум O(H), где применяются — не знаю.
Если нужно проводить несколько поисков одной «иголки» в разных «стогах», нужна всего одна предобработка.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
GigAnt Санкт-Петербург
от 200 000 ₽
Яндекс Москва
от 100 000 до 300 000 ₽
Clain Санкт-Петербург
от 350 000 ₽
16 окт. 2021, в 18:12
50000 руб./за проект
16 окт. 2021, в 17:28
20000 руб./за проект