Блог пользователя tril0713

help on hacking hash
Автор tril0713, история, 2 года назад, По-английски
Problem statement

We transform the condition $$$s_i \ne s_{n-i+1}$$$ into if we change all $$$\texttt{0} \to \texttt{1},\texttt{1} \to \texttt{0}$$$ and reverse it to get a string $$$t$$$, $$$s$$$ is good if and only if $$$s = t$$$. Then we can use suffix array or manachar to get the answer.

Then, the hash solution did the same transformation and use hashing to get the answer with $$$\text{base} = 10^9+7$$$ and $$$\text{mod} = 2^{64}-1$$$ (unsigned long long). Can it be hacked? I have done stress test for $$$15000$$$ test cases :(

I will provide the hash code and the suffix array code below, if you need to make a stress test.

SA code
hash code
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +10 Проголосовать: не нравится

Your solution uses unsigned long long overflows, so the hash modulo is $$$2^{64}$$$, not $$$2^{64} - 1$$$. It is well known that this hash is awful and the key is Thue-Morse sequence, see here.

The following generator hacks your solution instantly. For some reason, an assertion fails in the suffix array code if I specify n = 10'000, you might want to investigate it too.

int n = 5000;
cout << n << '\n';
for (int i = 0; i < n; ++i) {
    cout << __builtin_popcount(i) % 2;
}
cout << '\n';

On the other way, hash $$$2^{61} - 1$$$ seems to be a good alternative, I don't know any easy way to hack it. Birthday paradox attack probably can break it, but the probability is quite small, and if it happens, you should apply hashing with double moduli (two substrings are equal, iff both hashes coincide). I think, I haven't seen anywhere single hash modulo $$$2^{61} - 1$$$ failing. (However, you should do some bit tricks or use __int128 to multiply two numbers modulo $$$2^{61} - 1$$$. I use the latter and it works fine, but it might be unsupported somewhere)

You might want to read about hashes further, there are really many articles in the net, for example this or this.

→ Ответить