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

<p><a href="http://dx.doi.org/10.1016/j.jda.2014.08.001" rel="nofollow">A subquadratic algorithm for minimum palindrome factorization</a> by Fici <em>et al</em></p>

<p><a href="http://arxiv.org/abs/1506.04862" rel="nofollow">EERTREE: An Efficient Data Structure for Processing Palindromes in Strings</a> by Rubinchik and Shur.</p>

CC BY-SA 3.0
2015-10-06T12:10:40.120Z
2015-11-03T06:01:36.967Z
2015-11-03T06:01:36.967Z
Yu-Han Lyu
<p>Given a string <span class="math-container">$w=\sigma_1\sigma_2\ldots\sigma_n$</span>, a <em>palindrome cover</em> is a sequence <span class="math-container">$p_1p_2\cdots p_m$</span> of words <span class="math-container">$p_i$</span> such that <span class="math-container">$p_1p_2\cdots p_m = w$</span> and such that each <span class="math-container">$p_i$</span> is a palindrome.</p>
<blockquote>
<p>How hard is it to find the size minimal palindrome cover? (this seems doable by dynamic programming, but I'm not sure it works).</p>
<p>Does the problem become harder if given as input is also a bound <span class="math-container">$b$</span> on each palindrome length?</p>
</blockquote>
<p>Consider the simple greedy algorithm, which always takes the longest palindrome which starts at the current location. For example, if <span class="math-container">$w=1213312$</span>, then it'll output <span class="math-container">$(121)\cdot(33)\cdot(1)\cdot(2)$</span>, while the optimal cover is <span class="math-container">$(1)\cdot(213312)$</span>.</p>
<blockquote>
<p>Does the greedy algorithm provide 2-approximation for the problem?</p>
</blockquote>

<ds.algorithms><dynamic-programming><string-matching><covering-problems>
Covering string by palindromes
Dean R
# Covering string by palindromes

(Asked by: username_0 on 2015-10-06)

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?

**Tags:** ds.algorithms, dynamic-programming, string-matching, covering-problems

---

## 1 answers

### Answer by username_1 on 2015-10-06. Score: 9

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](http://dx.doi.org/10.1016/j.jda.2014.08.001) by Fici *et al*

[EERTREE: An Efficient Data Structure for Processing Palindromes in Strings](http://arxiv.org/abs/1506.04862) by Rubinchik and Shur.


---

