If overlapping is allowed, it can be done in linear time (in the size of the input string).
Some definitions
Let's define the concept of maximal palindrome:
A maximal palindrome of radius k of a string S is a substring S' such that
- starting from the centre, S' reads the same k characters in both directions
- but not for k+1 characters
- k > 1 (so a single character is not a palindrome)
for example, if S = banana
, then S' = anana
is a maximal palindrome of radius 2.
A maximal palindrome is a maximal palindrome of radius k for some k.
For example, if S = banana
, "ana"
, "anana"
, are all its maximal palindromes.
Using maximal palindromes
Now, if we could locate all maximal palindromes of a string, it would be simple to check if the whole string is a concatenation of palindromes.
Take S = abbaccazayaz
. Its maximal palindromes are:
- abba, centered between position 2 and 3, radius = 2
- acca, centered between position 5 and 6, radius = 2
- zayaz, centered in position 10, radius = 2
so "abba" spans over [1..4], "acca" spans over [4..7], "zayaz" spans over [8..12]. Since the concatenation of this three palindromes (overlapping is permitted?) spans over the whole string, it follows that "abbaccazayaz" is concatenation of palindromes.
Computing maximal palindromes in linear time
Now, it turns out that we can locate all maximal palindromes of a string S in linear time! *
The idea is to use a suffix tree for S equipped with constant-time lowest common ancestor queries.
So we can check if a string S of length m is a concatenation of palindromes in O(n) time.
*
Gusfield, Dan (1997), "9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences