Какая сложность наихудшего случая для KMP, когда цель состоит в том, чтобы найти все вхождения определенной строки?

Я также хотел бы знать, какой алгоритм имеет наихудшую сложность из всех для поиска всех вхождений одной строки в другую. Похоже, что алгоритм Бойера – Мура имеет линейную временную сложность.