# palindromic factorization

Is there a linear time algorithm that, given a string of length n, tells if it is a sequence of non overlapping palindromes (each of even length, in a binary alphabet)?? I found algorithms that return the longest palindrome, but this does not apply since a string like "aabbaabb" should be accepted since it can be divided in four palindromes.

I can't come up with an idea that works in linear time since I think that there could be cases in which a certain factorization is not a sequence of palindromes but another one is.

• There are several recent algorithms for finding the minimal palindromic partition of a string, running in time $O(n\log n)$, for example arxiv.org/pdf/1403.2431.pdf and the papers it references. While you have the additional constraint that all palindromes be even, perhaps these algorithms can be modified to accommodate this constraint. – Yuval Filmus Sep 15 '15 at 14:49
• Here is one paper that solves the minimal palindromic partition problem in $\Theta(n)$ time: Paper Slides – Terence Hang Sep 15 '15 at 16:40