полиномиальный хеш aka кольцевой хеш Рабина-Карпа aka хеш для олимпиад...

[_winnie]

при использовании "естественного" модуля 2^64 ломается вот таким неожиданно красивым образом:
http://codeforces.com/blog/entry/4898

Comments

[aamonster]

Красиво. Но, я так понимаю, в реальной жизни все держат в голове, что это "плохой" хэш, и для чего-то серьёзнее, чем "быстрая сигнатура" rsync или хэш для хэш-таблицы (когда коллизии приведут лишь к падению производительности, но не к некорректному результату) не используют?

[kodt_rsdn]

Читеры-организаторы против читеров-олимпиадников, которым лень следить за коллизиями?

А предупреждённые олимпиадники будут считать в кольце 2**64-1, чтоб нефиг.
А организаторы подберут коллизию и под такой хеш...

[_winnie]

> А предупреждённые олимпиадники будут считать в кольце 2**64-1

Там в обсуждении стоны, что в таком случае придётся использовать два 32-битных хеша. Видимо, в олимпиадных компиляторах использовать один модуль (2**64-1) сильно сложнее, чем два 32-битных модуля.

[kodt_rsdn]

Так не спасёт же! Если строка Туэ-Морса длиной 2^11 гарантированно приводит к коллизии 64-битного хеша, то на 32-битном тем более будет коллизия.

[_winnie]

Два 32-битных хеша по двум разным 32-битным модулям, имеется ввиду.

[creatorcray]

"means string after changing A **на** B and vice versa"

доставило!