Асимптотическая сложность худшего случая алгоритма Бойера-Мура + правило Галиля

Всем привет! Есть вопрос относительно асимптотической сложности алгоритма Бойера-Мура. С одной стороны, в большинстве источников написано, что худший случай это когда есть исходный текст, например, "ааааааааа" и шаблон(образ) "аааа", в таком случае асимптотическая сложность - О(n*m), где n - длина исходного текста, m - длина шаблона. С другой стороны, есть еще информация, что худший случай имеет сложность О(n+m). Не понятно, при каком исходном тексте и шаблоне можно получить такую сложность?

Также не совсем понятной является связь правила Галиля и алгоритма Бойера-Мура.