I'm trying to solve this problem: http://www.codeforces.com/problemset/problem/7/D
And here is my solution: http://www.codeforces.com/contest/7/submission/2865747
My code might look little bit ugly, because I tried to optimize it as much as I can, it's linear solution but it's getting TLE. Why is the time limit so strict like this? Is there any optimizations I can make? I think my solution is the intended solution.
Edit: I got it accepted after pre-computing all the powers instead of using my power function.
Are you using string hashes modulo 2*10^9?
I'm using string hashes modulo 2,000,000,063.
Beware, there were tons of tricks (in Russian)!
Shortly,
a) hashes modulo 2^N are very bad and can be hacked by a special test.
b.1) known single polynomial hash with small modulo (like this) can be hacked by test with about 20 length just by birthday paradox.
b.2) there is special algorithm for hacking any known polynomial hash with arbitary modulo.
c) double hashing with short known arguments can be hacked with a test like 400 length.
Try to randomize your hash parameters and use double hashing, or you can be suddenly hacked.
Good luck!
Thanks for the informations, actually sometimes I use triple hashing. But for most of the problems single hashing is enough if there is no challenges/hacks.
Single hashing is not enough if there are good tests.
Let us denote some prime modulo p and strings s1[i] and s2[i]. Strings s1 and s2 will be collision for roots of (s1[i]-s2[i])*x^i (mod p) polynomial. I don't know the estimation, but I think that it is about one root at mean. If so and if each test requires O(length(s)) hash checks, random testset will cover ALL of x in about O(p*log(p)/length^2(s)) time. For modulo about 2*10^9 this is a very little number.