Изменения
→Надёжность
Если количество подстрок данной строки превышает количество хешей, то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.
Например если взять <tex> r = 2^{32}, p = 237 </tex>, возьмем за <tex> s S</tex> принять [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]</ref> длиной <tex> 1024 2^{k}</tex>, <tex>r = 2^{64}</tex>, <tex>p</tex> - любое просто число. Обозначим за <tex>S_k</tex> строку <tex>S</tex> для фиксированного <tex>k</tex> , а за <tex>not S_k</tex> строку после замены <tex>A</tex> на <tex>B</tex> и наоборот. Покажем, что при <tex>k = 10</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(not S_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>not S_k</tex> встретятся в б''о''льших строках много-много раз. Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(not S_k)</tex>. Можно смело взять вместо <tex>A</tex> и <tex>B</tex> нули и единицы в коэффициентах многочлена - тем самым мы просто сократим обе части на <tex>\sum_{i=0}^{i<2^k} 65 \cdot p^i</tex>. Что такое <tex>\mathrm{hash}(S_k) - \mathrm{hash}(not S_k)</tex>? Нетрудно сообразить, что эта величина есть: <tex>T = p^{0} - p^{1} - p^{2} + p^{3} - p^{4} + p^{5} + p^{6} - p^{7} ... \pm p^{2^k - 1}</tex>. То есть это знакопеременная сумма степеней <tex>p</tex>, где знаки чередуются по тому же правилу, что и символы в строке. Будем последовательно выносить из этой суммы множители за скобку: <tex>T = (p^{1} - 1)( - p^{0} + p^{2} + p^{4} - p^{6} + p^{8} - p^{10} - p^{12} + p^{14} ...) = </tex> <tex> = (p^{1} - 1)(p^{2} - 1)(p^{0} - p^{4} - p^{8} + p^{12} ...) = ... = (p^{1} - 1)(p^{2} - 1)(p^{4} - 1) ... (p^{2^{k-1}} - 1).</tex> А теперь самое главное - эта величина по модулю <tex>2^{64}</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^{2Q - 1} - 1)</tex> делится по меньшей мере на <tex>2 \cdot 2^2 \cdot 2^3 \cdot ... = 2^{k(k - 1) / 2}</tex>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в половине случаеврассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.
== См. также ==
