?

Log in

No account? Create an account
nyaload

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

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

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


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

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

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

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

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

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

  • 1