==Алгоритм==
У нас есть Есть шаблон - <tex>p[1..m]</tex>. У нас есть и строка - <tex>s[1..n]</tex>. Мы хотим Нужно найти все вхождения шаблона в строку.
Давайте посчитаем В начале вычисляются <tex>hash(s[1..m])</tex> и <tex>hash(p[1..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>;) или мы проверяемпроверяется, что подстрока является шаблоном, для этого выберем выбираются и сравниваются случайные символы из строк и сравним их.
Следует предподсчитать <tex>p^{m}</tex>.
