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>.
