Изменения

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

Следует использовать полиномиальный хеш {{- --}} <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>p[1..m]</tex> и строка {{--- }} <tex>s[1..n]</tex>. Нужно найти все вхождения шаблона в строку.

Для <tex>i \in [1..n - m + 1]</tex> вычисляется <tex>hash(s[i..i + m - 1]</tex> и сравнивается с <tex>hash(p[1..m])</tex>. Если они получаются равными {{- --}} то считается, что подстрока <tex>p</tex> входит в строку <tex>s</tex> (начиная с позиции <tex>i</tex>;) или проверяется, что подстрока является шаблоном, для этого выбираются и сравниваются случайные символы из строк.

Новый хеш <tex>h </tex> был получен с помощью быстрого пересчёта. Следует считать, что <tex>s[n + 1] </tex> - пустой символ.

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

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — {{---}} 2-е изд. — {{---}} М.: Издательский дом «Вильямс», 2007. — {{---}} С. 1296.