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.

  • 1
    $\begingroup$ 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. $\endgroup$ Sep 15, 2015 at 14:49
  • 2
    $\begingroup$ Here is one paper that solves the minimal palindromic partition problem in $\Theta(n)$ time: Paper Slides $\endgroup$ Sep 15, 2015 at 16:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.