Help in IGNUS14B

I’m trying to solve the problem Prime Palindromes(IGNUS14B) Link-IGNUS14B Problem - CodeChef

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:-svJ7ot - Online C++ Compiler & Debugging Tool - Ideone.com

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