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

Answer 2

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 3

Consider a string S="aaabb".

Append a character '$' at both ends of the string and in between every two consecutive characters to change the string to S="$a$a$a$b$b$" and apply Manacher's algorithm for this string S.

New string S is of length 2n+1 which gives us runtime of O(2n+1) which is same as O(n).

index :  1 2 3 4 5 6 7 8 9 10 11
A     :  1 3 5 7 5 3 1 3 5  3  1
S     :  $ a $ a $ a $ b $  b  $

Array A is the result of Manacher's Algorithm.

Now, the summation of A[i]/4 for index where '$', else (A[i]+1)/4 for every other character from 1<=i<=n is your answer.

Here, $ acts as a center for the even length palidromic substrings and the odd length can be calculated normally. The answer for this case is:

0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a,a,aaa,a,b,b,aa,aa,bb).