У каждого из этих алгоритмов есть пара свойств, которые могут сделать их желательными или нежелательными в различных обстоятельствах.Вот краткое изложение:
Космическое использование благоприятствует Рабину-Карпу
Одним из основных преимуществ Рабина-Карпа является то, что он использует O (1) вспомогательного пространства для хранения, что хорошо, если вы используете строку шаблонаИщите очень большой.Например, если вы ищете все вхождения строки длиной 10 7 в более длинной строке длиной 10 9 , не нужно выделять таблицу 10 7 машинных слов для функции сбоя или таблицы смены - главный выигрыш.Как Бойер-Мур, так и KMP используют память Ω (n) для последовательности шаблонов длины n, поэтому Рабин-Карп выиграл бы здесь явно.
Рабин-Карп страдает от двух потенциально худших случаев.Во-первых, если конкретное простое число, используемое Рабином-Карпом, известно злонамеренному злоумышленнику, этот злоумышленник может потенциально создать вход, который заставляет скользящий хеш соответствовать хешу строки шаблона в каждый момент времени, что приводит к снижению производительностиухудшиться до Ω ((m - n + 1) n) на строке длиной m и образцом длины n.Если вы берете ненадежные строки в качестве входных данных, это может быть проблемой.Ни Бойер-Мур, ни KMP не имеют этих недостатков.
Эффективность множественных совпадений в наихудшем случае благоприятствует KMP.
Аналогично, Рабин-Карп работает медленно, если вы хотите найти все совпадениястрока шаблона в случае, когда этот шаблон появляется большое количество раз.Например, если вы ищете строку из 10 5 копий письма a в текстовой строке, состоящую из 10 9 копий письма a с Rabin-Карп, тогда будет много мест, где появится строка шаблона, и для каждого потребуется линейное сканирование.Это также может привести к времени выполнения Ω ((m + n - 1) n).
Многие реализации Бойера-Мура страдают от этого второго правила, но не будут иметь плохие времена выполнения в первом случае.И у KMP нет таких патологических наихудших случаев, как эти.
Лучшая производительность способствует Бойеру-Муру
Одним из преимуществ алгоритма Бойера-Мура является то, что он не обязательно должен сканировать всесимволы входной строки.В частности, правило неверных символов может использоваться для пропуска огромных областей входной строки в случае несоответствия.В частности, наилучшим временем выполнения для Бойера-Мура является O (m / n), что намного быстрее, чем может обеспечить Rabin-Karp или KMP.
Обобщения для множественных строк поддерживают KMP
Предположим, у вас есть фиксированный набор из нескольких текстовых строк, которые вы хотите искать, а не только одна.Вы можете, если хотите, запустить несколько проходов Рабина-Карпа, KMP или Бойера-Мура по всем строкам, чтобы найти все совпадения.Тем не менее, время выполнения этого подхода невелико, так как он линейно масштабируется с количеством строк для поиска.С другой стороны, KMP хорошо обобщает алгоритм сравнения строк Aho-Corasick, который выполняется за время O (m + n + z), где z - количество найденных совпадений, а n - объединенная длина строк шаблона.Обратите внимание, что здесь нет зависимости от количества искомых строк шаблона!