Кнут Моррис Пратт против Бойера Мура: двоичный алфавит против алфавита с большим количеством букв

Основное преимущество Boyer-Moore перед KMP состоит в том, что Boyer-Moore может иметь сублинейную среду выполнения. Однако это происходит, когда в шаблоне, который вы ищете, не так много несовпадающих символов (поскольку это позволяет алгоритму переходить дальше по тексту). В большом алфавите несовпадение символов вне шаблона более вероятно, поэтому Бойер-Мур, вероятно, лучший выбор. Однако имейте в виду, что в худшем случае BM выполняется в ~ MN, где M - размер шаблона, а N - размер текста, тогда как KMP гарантированно линейный.

Для двоичного алфавита я бы выбрал KMP. Символ несоответствия в BM почти всегда будет в шаблоне, поэтому вы, вероятно, будете двигаться по тексту линейно, и в этом случае между двумя алгоритмами будет небольшая разница. Однако в двоичном алфавите намного проще найти наихудший случай для BM, поэтому KMP более безопасен.