?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
полиномиальный хеш aka кольцевой хеш Рабина-Карпа aka хеш для олимпиад...
nyaload
_winnie
при использовании "естественного" модуля 2^64 ломается вот таким неожиданно красивым образом:
http://codeforces.com/blog/entry/4898
Tags: ,


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

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

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

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

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

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

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

Всё весьма просто - чтобы использовать хеш по модулю M обычно нужно не бояться, что число порядка M^2 влезет в стандартный тип данных(на олимпиадах сейчас таковым самым большим считается 64битный), иначе будет переполнение, когда попытаемся что-то перемножить. 2^64 было очень удобным потому, что о переполнении можно не беспокоиться, оно автоматически правильно возьмется по модулю.

В итоге теперь нужно пользоваться двумя разными модулями и вместо стандартного переполнения 64битного числа вручную вызывать операцию деления с остатком, что напрочь убивает всю производительность.

Предупрежденные генерят рандомный модуль, желательно простой, и считают по нему.

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

доставило!

  • 1