Бойер-Мур строка алгоритма поиска времени выполнения сложности

Question

В Boyer-Moore string search algorithm wiki ссылке указывается, что в худшем случае сложность Бойер-Мура является

1. O (т + п), если изображение не отображается в текст
2. о (млн), если паттерн появляется в тексте

Но в String Search Algorithm wiki указано, что наихудшая сложность Boyer-Moore составляет O (n). Почему это несоответствие?

Here также указано, что O (mn) в худшем случае.

Итак, какова правильная временная сложность алгоритма Boyer-Moore?

Answer 1

Разница исходит из разных определений. На общей странице поиска строк сложность алгоритмов разделяется на предварительную обработку и сопоставление, тогда как сама страница для самого алгоритма не делает этого различия.

Предварительная обработка будет равна Θ (m + k) плюс O (n) для согласования.