Zakrywający sznur palindromami

Biorąc pod uwagę ciąg , okładka palindromu jest sekwencją słów tak że i takie, że każdy jest palindromem.$w=\sigma_1\sigma_2\ldots\sigma_n$$p_1p_2\cdots p_m$$p_i$$p_1p_2\cdots p_m = w$$p_i$

Jak trudno jest znaleźć minimalną wielkość palindromu? (wydaje się to wykonalne przez programowanie dynamiczne, ale nie jestem pewien, czy to działa).

Czy problem staje się trudniejszy, jeśli podany jako dane wejściowe jest również związany na każdej długości palindromu?$b$

Rozważ prosty algorytm zachłanny, który zawsze zajmuje najdłuższy palindrom, który zaczyna się w bieżącej lokalizacji. Na przykład, jeśli$w=1213312$ , to wyświetli , podczas gdy optymalne pokrycie to ( 1 ) ⋅ ( 213312 ) .$(121)\cdot(33)\cdot(1)\cdot(2)$$(1)\cdot(213312)$

Czy chciwy algorytm zapewnia przybliżenie 2 dla problemu?

$O(n \log n)$

Podkwadratowy algorytm minimalizacji faktoryzacji palindromu autorstwa Fici i in

EERTREE: Wydajna struktura danych do przetwarzania palindromów w ciągach znaków Rubinchika i Shura.