We know that we can solve this problem using Suffix Arrays and Suffix Trees in Linear Time, but its not all that nice. I will probably like to implement the components of those some time. But there is a much nicer and simpler algorithm, called “Manacher’s Algorithm” that I had known, but never bothered reading up on. Dhruv, today shared a link which explained it brilliantly. Here it is.

I will try to solve NUMOFPAL on SPOJ using Manacher’s. I might also do EPALIN, which I already did earlier using an approach similar to Karp-Rabin.

Update: I solved NUMOFPAL using Manacher’s.