Few Lessons About Rabin Karp after 73 Wrong Answers

Link: http://codeforces.com/contest/113/problem/B

It is indeed quite easy to produce collisions, ie make more than one string map to the same hash value.

However, it is VERY difficult to produce collisions of strings with the SAME SIZE.

Yet, even if this was possible, it is way harder to produce collisions with the same size AND same middle character.

So, instead of storing the hash, concatenate it (bitwise) with the length of the string and the middle character.

That would be a good enough way for handling collisions.

Also, for some reason this pair of base and modulus is the only one that worked to pass test case #29:

int B=29;
int M=(1ll<<31)-1;

Also, instead of using set.insert, just use vector.push_back then at the very end sort and count the unique elments. This reduced the time from 1716 ms to 404 ms !