Алгоритм KMP выполняет меньше сравнений, чем упрощенный алгоритм Бойера-Мура?

Question

Алгоритм KMP выполняет меньше сравнений, чем упрощенный алгоритм Бойера-Мура?

Выполняет ли алгоритм КМП (Кнута-Морриса-Пратта) меньше сравнений, чем упрощенный алгоритм Бойера-Мура?

2

string-search boyer-moore

Источник

user472801 24 ноя '10 в 03:21

1 ответ

Решение

Другие вопросы по тегам string-search boyer-moore

user42303 24 ноя '10 в 03:48 2010-11-24 03:48 · Accepted Answer · 2010-11-24 03:48

Алгоритм Бойерса Мура обычно должен работать с меньшим количеством сравнений, чтобы цитировать отсюда

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