Изменения
Нет описания правки
Получается, что <tex>(p^1 - 1)(p^2 - 1)(p^4 - 1)...(p^{2k - 1} - 1)</tex> делится по меньшей мере на <tex>2 \cdot 2^2 \cdot 2^3 \cdot ... = 2^{k(k - 1) / 2}</tex>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.
== Сравнение с другими алгоритмами ==
=== Преимущества ===
* Быстрая скорость работы - <tex>O(n + m)</tex>, где <tex>n</tex> - длина строки, <tex>m</tex> - длина образца.
* Простая и понятная реализация.
=== Недостатки ===
* Возможно подобрать входные данные, так, что количество ложных срабатываний будет недопустимо большим.
== См. также ==
