11
$\begingroup$

Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome.

How hard is it to find the size minimal palindrome cover? (this seems doable by dynamic programming, but I'm not sure it works).

Does the problem become harder if given as input is also a bound $b$ on each palindrome length?

Consider the simple greedy algorithm, which always takes the longest palindrome which starts at the current location. For example, if $w=1213312$, then it'll output $(121)\cdot(33)\cdot(1)\cdot(2)$, while the optimal cover is $(1)\cdot(213312)$.

Does the greedy algorithm provide 2-approximation for the problem?

$\endgroup$
0

1 Answer 1

9
$\begingroup$

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example:

A subquadratic algorithm for minimum palindrome factorization by Fici et al

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.