Help in IGNUS14B

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.

2 Likes
//