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).