Изменения

Выберем полиномиальный хеш - <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>O(1)</tex>:

<tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i + 1..i + m- 1]) + s[i + m]</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>;)или мы проверяем, что подстрока является шаблоном, для этого выберем случайные символы из строк и сравним их.