Изменения

Алгоритм Рабина — Карпа — это алгоритм поиска подстроки в строке, используя хеширование.

Выберем полиномиальный хеш - <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])</tex> mod <tex>r</tex>, где <tex>p</tex> - это некоторое простое число, а <tex>r</tex> - некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически - при переполнении типов;). Заметим, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.

Получается : <tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]</tex>.

У нас есть шаблон - <tex>p[1..m]</tex>. У нас есть строка - <tex>s[1..n]</tex>. Мы хотим найти все вхождения шаблона в строку.

Следует предподсчитать <tex>p^{m}</tex>.

Изначальный подсчёт хешей - <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций - каждая выполняется за <tex>O(1)</tex>. Итого - <tex>O(n + m)</tex>.