Finding Number of Palindromic Substrings in O(n) or O(n log n)?

Question

I know you can find the longest palindromic substring in O(n) with manacher's algorithm, but is it possible to find the total number of palindromic substrings in O(n) or O(n log n)? If so, how would you go about doing it?

Count single letters as palindromes too.

---

So for example, the number of palindromic substrings of "xyxyx" is 9.

This is because you have:

5 single letter palindromes (x,y,x,y,x)
3 palindromes with three letters (xyx, yxy, xyx)
1 palindrome with five letters (xyxyx)

for a total of 5+3+1 = 9 palindromic substrings.

Answer 1

A substring S' of a string S is a maximal palindrome of radius i iff starting at the middle it reads the same in both directions for i characters, but not for i+1 characters.

Any palindrome in a string must be a substring of a maximal palindrome with the same center. Conversely, every substring of a maximal palindrome with the same center must also be a palindrome. We can also easily count the number of sub-palindromes with the same center: a palindrome of length k contains Ceiling(k/2) of them.

Seeing as we can find all maximal palindromes using Manacher's algorithm in linear time, we have a linear time algorithm for your problem: find the array of lengths of the maximal palindromes, divide by two, take the ceiling, sum the array.

Example 1: on "xyxyx", the maximal palindromes are

x, xyx, xyxyx, xyx, x

and Manacher's can be used to calculate an array

1, 0, 3, 0, 5, 0, 3, 0, 1

representing the lengths of the maximal palindromes centered at each letter and in each gap between letters. Anyway, applying the map Ceiling(k/2) to the entries, we get

1, 0, 2, 0, 3, 0, 2, 0, 1

which sums to 9.

Example 2: "abba". Maximal palindromes are

a, b, abba, b, a

Manacher's can be used to get the array

1, 0, 1, 4, 1, 0, 1

and the Ceiling(k/2)'d array is

1, 0, 1, 2, 1, 0, 1

for a sum of 6 (a, b, b, a, bb, abba).