Изменения
→Пример худшего случая
Обозначим за <tex>S_k</tex> строку <tex>S</tex> для фиксированного <tex>k</tex> , а за <tex>S'_k</tex> инвертированную строку <tex>S</tex>.
Покажем, что при <tex>k = 10< 12</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>S'_k</tex> встретятся в б''о''льших строках много-много раз.
Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Можно смело заменить коды символов на нули и единицы в коэффициентах многочлена — тем самым мы просто сократим обе части на <tex>\sum\limits_{i=0}^{2^k - 1} 65 \cdot p^i</tex>.
Нужно понять, на какую максимальную степень двойки делится каждая из <tex>k - 1</tex> скобок. Заметим, что <tex>(i + 1)</tex>-ая скобка <tex>p^{2^{i + 1}} - 1 = (p^{2i} - 1)(p^{2i} + 1)</tex> делится на <tex>i</tex>-ую и ещё на какое-то чётное число <tex>p^{2i} + 1</tex>. Это означает, что если <tex>i</tex>-ая скобка делится на <tex>2^r</tex>, то <tex>(i + 1)</tex>-ая скобка делится по меньшей мере на <tex>2^{r + 1}</tex>.
Получается, что <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>. Мы показали, что если k < 12, то величина <tex>\mathrm{hash}(S_k) - \mathrm{hash}(S'_k) = 0</tex>, то есть <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.
== Сравнение с другими алгоритмами ==
