Работая со строками, возникает часто задача поиска подстроки в строке (каждый текст мы можем представить в виде одной строки, используя спец. символы: \n и т.д.)

Пусть задана строка s из N элементов и строка q из M элементов. Здесь мы подразумеваем, что q - не пуста и M ≤ N.

Строку s мы назовем текстом, строку q - образцом.

Ставится задача: определить, содержит ли текст s образец q, и, в случае положительного результата, выдать позицию k в тексте s, с которой начинается вхождение q в s.

Задача прямого поиска заключается в поиске индекса k, указывающего на первое с начала текста s совпадение с шаблоном q.

Наивное решение такой задачи: поэлементное сравнение всех символов q[i] из шаблона с символами s[j] текста. Такая реализация подразумевает сложность O(N * M) - слишком медленно, можно улучшить асимптотику.

P.S. такая сложность будет происходить, если текст имеет вид

АААААААААААААААААААААААААААААААА.....ААААААААВ

А шаблон содержит ту же идею, но поменьше Ашек

ААААААА....ААААВ

Одним из подходов к улучшению наивной реализации решения задачи поиска подстроки в строке является алгоритм Рабина-Карпа.

Вместо того, чтобы использовать более умный пропуск (Бойер-Мур), алгоритм Рабина — Карпа пытается ускорить проверку эквивалентности образца с подстроками в тексте, используя хеш-функцию. Хеш-функция — это функция, преобразующая каждую строку в числовое значение, называемое хеш-значением (или просто хеш).

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

Однако, это не совсем так... Существуют две проблемы:

1. Между двумя различными строками может произойти коллизия — совпадение их хешей. Для избежания ложного срабатывания приходится всё равно проверять в итоге шаблон с подстрокой текста. Минимизация коллизий: подбор "хорошей" хеш-функции.
2. Подсчет следующих хеш-значений. Считать заново неэффективно, потеряем в скорости.

Для избежания частых коллизий используется полиномиальный хеш. Для данного шаблона q длины M такой хеш будет определен следующим образом:

В данной формуле x может быть любым числом от 1 до (p - 1). p берут большим числом для работы в кольце вычетов по модулю p. Для простоты можно не писать часть mod p, а под x взять небольшое простое число, чтобы не выйти за пределы типа - такое решение тоже имеет место на жизнь.

Соответственно, по этой формуле, единой для всей программы, будут вычисляться и хеши подстрок в тексте.