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.
Update: I solved NUMOFPAL using Manacher’s.