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