Zakrywający sznur palindromami

12

Biorąc pod uwagę ciąg , okładka palindromu jest sekwencją słów tak że i takie, że każdy jest palindromem.w=σ1σ2σnp1p2pmpip1p2pm=wpi

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śliw=1213312 , to wyświetli , podczas gdy optymalne pokrycie to ( 1 ) ( 213312 ) .(121)(33)(1)(2)(1)(213312)

Czy chciwy algorytm zapewnia przybliżenie 2 dla problemu?

Dean R.
źródło

Odpowiedzi: