Nice problem
@hemanth_1 I tried your hash method and it works. I don’t see why it would be 6*Log(Mod) operations though, 6 is enough.
can you please share your code ?
Here it is: wv8Dj1 - Online C++0x Compiler & Debugging Tool - Ideone.com
I am sure it’s a bit difficult to understand it.
@vivek_1998299 a polynomial hash like you mentioned: hash_2(n) = \sum_p (cnt_n(p) \bmod 2) \cdot base ^ p \mod M where p is prime and cnt_n(p) is the number of times p divides n. It is similar for hash_3. If you want the code: link.
@meooow Yeah you’re right, 6 is enough. I was thinking of taking a prime close to the length of the string as ‘Mod’, and use binary exponentiation for updating. I saw a different hash function here : https://threads-iiith.quora.com/String-Hashing-for-competitive-programming . But we can precompute powers instead.
@hemant i tried using the hash function u mentioned in one of my past hackerrank question,however couldnt get AC(got 50/55) due to collisions.Plz tell if u could find a perfect value of p,mod
(Particularly for strings with 26 characters)
@hemanth_1 actually the hash I used is the same as the one described in that article. Here you can consider the character S_i is cnt_n(i) \bmod 2 when i is prime and 0 when it is not. The difference from the string case is that, as you said when describing the approach, here from hash(x) to hash(xy) some characters change instead of only a new character being added.