[Править]Недостатки

• Требует   операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше).

    Алгоритм Рабина-Карпа

Алгоритм  Рабина-Карпа

Рабин и Карп изобрели алгоритм поиска подстрок, который эффективен на практике и к тому же обобщается на другие аналогичные задачи. В среднем он работает достаточно быстро.

Предположим для начала, что Х = {0, 1, 2, ..., 9} (в общем случае можно считать, что каждый символ в алфавите Х есть d-ичная цифра, где d= |Х|). Тогда строку из k символов можно рассматривать как десятичную запись числа (k-значного), а сами символы как цифры.

Если P[1..т] — образец, то через p обозначим число, десятичной записью которого он является; аналогично, если T[1..n] — текст, то для всех значений s =0,1,..., n-m обозначим через t_s число, десятичной записью которого является строка T[s+ 1 .. s+ т]. Очевидно, s является допустимым сдвигом тогда и только тогда, когда t_s= p. Если бы мы могли вычислить p за время О(m) и все t_i,-за время O(n), то мы смогли бы найти все допустимые сдвиги за время О(n), сравнивая р со всеми t_s по очереди.

Вычислить р за время О(m) действительно можно, используя схему Горнера:

P= Р[m] + 10(Р[m-1 ]+ 10(Р[m-2 ]+ ...+ 10(P[2]+ P[1])...)).

Точно так же за время O(m) можно вычислить t₀.

Чтобы вычислить t₁,t₂,…t_n-m за время O(n -m), можно воспользоваться формулой

t_s+1= 10(t_s-10^m-1T[s+1])+T[s+m+1].

До сих пор мы не учитывали того, что числа р и t велики — настолько, что предположение о выполнении арифметических операций за время 0(1) едва ли допустимо. К счастью, эту трудность можно обойти следующим образом: надо проводить вычисления чисел р и t₀ по модулю фиксированного числа q. Тогда все числа не превосходят q и можно считать, что число р и все tj будут действительно вычислены за время 0(n+ m). Обычно в качестве q выбирают простое число, для которого 10q помещается в машинное слово - это упрощает программирование вычислений. В общем случае (для алфавита {0, 1, 2, ..., d}) выбирают такое простое число d, что dq помещается в машинное слово (благодаря этому все арифметические операции происходят в пределах одного слова); последнее рекуррентное соотношение приобретает вид

t_s+1=(d(t_s-T[s+1]h)+T{s+m+1}mod q, где h = d^m-1 (mod q).

Вычисления по модулю q хороши всем, кроме одного: из равенства t_s = p (mod q) еще не следует, что t_s =p. Поэтому, если t_s ≠ p (mod q), то сдвиг s заведомо недопустим и о нем можно забыть, а если t_s = p (mod q) , то надо еще проверить, совпадают ли строки Р[1..m] и T[s+1..s + m] на самом деле. Если совпадают, то мы нашли вхождение образца в строку, а если не совпадают, то произошло холостое срабатывание (spurious hit). Если простое число q достаточно велико, то можно надеяться, что дополнительные затраты на анализ холостых срабатываний будут невелики.

Метод хеширования

Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать:  , где   — это некоторое простое число, а   — некоторое большое число, для уменьшения числа коллизий (обычно берётся   или  , чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.

При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за  :

.

.

Получается :  .