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

Question

[Alpendev2876]

Как должны выглядеть разные уровни сложности алгоритмов для определения строки в другой строке в качестве подстроки?

Answer 1

[Армянское Радио]

Они должны выглядеть как алгоритм Ахо-Корасик, который имеет линейную сложность и является наиболее оптимальными.

Answer 2

[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), где применяются — не знаю.
Если нужно проводить несколько поисков одной «иголки» в разных «стогах», нужна всего одна предобработка.