I am trying to solve this problem for a long time https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=588&page=show_problem&problem=4450
obviously the brute force will TLE, any O(n^2) algorithm will TLE and any use of suffix array will also TLE.
So what I need actually is to find a way to hash the string from left and right and this requires a hashing function that hashes a string as it hashes his reverse.
Is this possible or there is another way to solve the problem.
http://www.suhendry.net/blog/?p=1699&page=7
It's either the hashing function is wrong or there is a bug in my code http://ideone.com/d1ADUG
your hasing function seems wrong and careful with integer overflow or big-integer because it's slow.
I didn't get it because even if I do change the the prime number to 3 or 73 or any small prime the code still fails.
even if you change to smallest prime = 2; 2^10000 is also very big integer.
Then what should I do. I just followed that editorial
Of course, that editorial exclude modulo operation ;) You can use modulo to avoid large integer.
Actually I know this. But I usually have problems in how to choose the prime that I will multiply with and the prime that I will take it's modulo.
Actually 1000000007 and 1000000009 will fail because they are not far from each other.
refresh the code link. I have chosen 73 and 1000000009.
I really have a problem with choosing the primes.
well, because it's hash function, you can try any prime combination, and see if the code getting AC or not. and btw, there is a mistake in that editorial, "L = L * P + S[i]" should be "L = L * x + S[i]".
I believe there is a problem in the function itself.
Because when we enter a string like paspas it gives 1 (Actually 3 characters will not lead to any overflows or big numbers) when it should give 2.
Got it accepted by the help of one of my university coaches. There is a bug in the editorial. L should be multiplied with x not p.