Выполняет ли алгоритм KMP (Кнут-Моррис-Пратт) меньше сравнений, чем упрощенный алгоритм Бойера-Мура?
Алгоритм Бойерса Мура обычно должен работать с меньшим количеством сравнений, чтобы цитировать из здесь
Должно быть достаточно ясно, что, если это обычно так, данная буква непоявляются в строке поиска вообще, тогда этот алгоритм требует только приблизительно N / M сравнений символов (N = длина (s1), M = длина (s2)) - большое улучшение алгоритма KMP, которое все еще требует N. Однако,если это не так, то нам может потребоваться до N + M сравнений снова (с полной версией алгоритма).К счастью, для многих приложений мы приближаемся к производительности N / M.Если строка поиска очень большая, то, скорее всего, в ней появится заданный символ, но мы все равно получим хорошее улучшение по сравнению с другими алгоритмами (приблизительно N * 2 / alphabet_size, если символы случайно распределены в строке).