Bizda quyidagi matn bor bo’lsin

Хеш-функция

С применением хеш-функции связаны два нюанса.
Во-первых, алгоритм хорош настолько, насколько хороша его хеш-функция. Если при использовании хеш-функции имеют место многочисленные ложные срабатывания, то сравнение символов будет выполняться слишком часто. В этом случае очень сложно считать этот метод более эффективным, чем наивный алгоритм.
Во-вторых, каждый раз, когда подстрока проходит по тексту, вычисляется новый хеш, что крайне неэффективно, ведь в этом случае производительность такая же, если не хуже, как у наивного алгоритма.
Обе эти проблемы решаются с помощью полиномиального хеша с операциями сложения и умножения. И хотя это не какой-то эксклюзив алгоритма Рабина-Карпа, которого нет в других алгоритмах, здесь он работает так же хорошо.

Полиномиальный кольцевой хеш

Вот как выглядит вычисление полиномиального хеша, построенного на операциях сложения у умножения:

c = символы в строке, m = длина строки, b = константа

Пример

Не будем заниматься преобразованием символов, а сразу используем целые числа.
Дан шаблон 135 и текст 2135 с основанием b = 10.
Сначала вычисляем хеш шаблона 135:

Затем вычисляем хеш первых m = 3 символов текста, т. е. 213:

Совпадения не произошло. Теперь сдвигаем подстроку, отбросив первый символ предыдущего окна и добавив следующий. Получилось новая 135. Вычисляем для неё хеш:

Хеши совпадают, и алгоритм фактически подходит к своему завершению.

Скользящий хеш

Обратите внимание: переместив сдвигающее, а лучше сказать, скользящую подстроку, нам пришлось вычислить весь хеш 213 и 135. А это нежелательно, так как при этом мы вычислили хеш целых чисел, которые уже были в предыдущем окне.
Скользящая хеш-функция может запросто устранить эти дополнительные вычисления, убрав из подсчёта хеша нового окна первый символ предыдущего и добавив новый символ.
Теоретически мы можем избавиться от хеш-значения этого убранного из подсчёта символа, умножить полученное значение на основание, чтобы восстановить правильный порядок степени предыдущих нетронутых символов, и добавить значение нового символа.
То есть мы можем вычислить хеш новой подстроки по этой формуле:

Hp = предыдущий хеш, Cp = предыдущий символ, Cn = новый символ, m = размер подстроки, b = константа
Используя предыдущий пример сдвига от 213 к 135, мы можем подключить эти значения для получения нового хеша:

Применяя скользящую хеш-функцию, можно вычислить хеш каждого скользящей подстроки за линейное время. Это основной компонент алгоритма Рабина-Карпа, обеспечивающий лучшее время исполнения O(n+m).