algorithm - Counting palindromic substrings in O(n)

Question

Given a string (assume only English characters) S of length n, we can count the number of palindromic substrings with the following algorithm:

for i = 0 to |S| do
    p1 = number of palindromes centered in i (odd length)
    p2 = number of palindromes centered in i and i+1 (even length)

    add p1 + p2 to total number of palindromic substrings of S

The above code is O(n^2) however.

I am interested in an algorithm that solves this problem in O(n). I know for sure that one exists as I've heard multiple people say that it does, and the problem exists on a local online judge site with an upper bound of 1 000 000 on n, however I've never seen the algorithm and can't seem to be able to come up with it.

Update:

The general idea I have is to compute len[i] = length of the longest palindrome centered at the character 2i + 1 and a similar array for even-length palindromes. With good bookkeeping, it should be possible to compute this in O(1) for each character, which will allow us to count a lot of palindromes all at once. I'm stuck on how exactly to compute this however.

I will accept a solution that uses O(n) and maybe even O(n log n) extra memory. I think this is impossible without it.

Any good ideas or references are appreciated.

Answer 1

The following site shows an algorithm for computing the longest palindromic substring in O(n) time, and does so by computing the longest palindromic substring at every possible center and then taking the maximum. So, you should be able to easily modify it for your purposes.

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

EDIT: The first link looks a little shaky upon closer inspection, so here's another one:

http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829