308
правок
Изменения
м
→Надёжность
== Надёжность ==
Если количество подстрок данной строки превышает количество хешей, то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где хеши выдают алгоритм на хешах выдаёт частые ложные срабатывания.
Например если взять <tex> r = 2^{32}, p = 237 </tex>, за <tex> s </tex> принять [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]</ref> длиной <tex> 1024 </tex> , то алгоритм находит лишние вхождения почти в половине случаев.
