Complexity of algorithms for determining a substring in a string?

Question

Algorithms

What should the different complexity levels of algorithms look like to determine a string in another string as a substring?

Answer 1

They should look like the Aho-Korasik algorithm, which has linear complexity and is the most optimal.

Answer 2

H = |haystack|, n = |needle|, a is the size of the alphabet.
Primitive algorithm: no preprocessing, work on average 2H, maximum O(Hn).
Typical fast algorithms: O(n) or O(n+a) preprocessing, average operation <H, maximum O(Hn).
Automatic algorithms: preprocessing O(na) or O(n+a), work =H.
There are TERRIBLE algorithms with work on average <H and a maximum of O (H), where they are applied - I don’t know.
If you need to conduct several searches for the same "needle" in different "stacks", you need only one pre-processing.