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

For "normal" strings it should be rather efficient to look at each character as the potential "center" of a palindrome and then check if the surrounding characters actually build one:

# check odd palindromes
for center in range(len(ls)):
   # check how many characters to the left and right of |center|
   # build a palindrome
   maxoffs = min(center, len(ls)-center-1)
   offs = 0
   while offs <= maxoffs and ls[center-offs] == ls[center+offs]:
      offs += 1
   offs -= 1
   print ls[center-offs : center+offs+1]                                    

# check for even palindromes
for center in range(len(ls)-1):
   maxoffs = min(center, len(ls)-center-2)
   offs = 0
   while offs <= maxoffs and ls[center-offs] == ls[center+offs+1]:
      offs += 1
   offs -= 1
   if offs >= 0:
      print ls[center-offs : center+offs+2]

For normal strings this should be about O(n), though in the worst case, for example if the string consists of only one character repeated over and over again, it will still take O(n²) time.

Answer 2

Fundamentally, such an algorithm is impossible. Consider the string which is all one characters- say, "aaaaa". The number of palindromes contained within is proportional to n^2. How can you count n^2 potential palindromes in n time? You can't, it's impossible. Therefore, no such algorithm exists for this case, and thus, the case in general.

Answer 3

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