304
правки
Изменения
→Алгоритм
В начале вычисляются <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>.
