Статья 2297

Возможно, что алгоритм Бойера и Мура работает быстрее, однако насколько можно быть уверенным в его правильности. В частности, как убедиться в том, что при сдвиге слова на несколько позиций вправо без попутных сравнений не было пропущено ни одной совпадающей группы литер. Содержательное объяснение состоит в том, что для полного совпадения необходима идентичность всех пар литер, между тем как группы, которые пропускаются, отличаются хотя бы в одной позиции, а именно в опорной позиции.
Правильность и эффективность - самые больные вопросы для программистов. Я уже указывал на то, что аналитические методы могут и должны использоваться для доказательства правильности программ, ибо даже для простых задач исчерпывающая экспериментальная проверка заняла бы слишком много времени. По этой же причине нельзя экспериментально оценить эффективность алгоритмов.