I’m trying to solve the problem Prime Palindromes(IGNUS14B) Link-http://www.codechef.com/problems/IGNUS14B
I have used Manacher’s algorithm in my solution.But it is not working for some cases example-ababac
where my solutions prints 3 instead of 4.
Link to my solution:-http://ideone.com/svJ7ot
Please help me?
Hi knb_dtu,
You will be getting values less than actual output because you are not counting ALL of the palindromic substrings.
The P[] matrix for your test case is 0 1 0 3 0 5 0 3 0 1 0 1 0.
As you can see you have 3 palindromic substrings centered @ idx=2,3,4(considering idx starts @ 1).
Now you are counting only these three substrins- “aba”(idx=2), “ababa”(idx=3) ,“aba”(idx=4).
But you are missing “bab” which is a substring of “ababa”. If you include this you would get the desired output.
So, you should not just have to count prime values of P[i] but also need to consider the substrings of each of these substrings. I hope you get my point.