@Alpendev2876

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

Как должны выглядеть разные уровни сложности алгоритмов для определения строки в другой строке в качестве подстроки?
  • Вопрос задан
  • 95 просмотров
Пригласить эксперта
Ответы на вопрос 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), где применяются — не знаю.
Если нужно проводить несколько поисков одной «иголки» в разных «стогах», нужна всего одна предобработка.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы