2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.