Cubriendo la cuerda por palíndromos

12

Dada una cadena , una cubierta de palíndromo es una secuencia p 1 p 2p m de palabras p i tal que p 1 p 2p m = w y tal que cada p i es un palíndromo .w=σ1σ2σnp1p2pmpip1p2pm=wpi

¿Qué tan difícil es encontrar el tamaño mínimo de la cubierta de palíndromo? (Esto parece factible mediante programación dinámica, pero no estoy seguro de que funcione).

¿El problema se vuelve más difícil si se da como entrada también es un límite en cada longitud de palíndromo?b

Considere el algoritmo codicioso simple, que siempre toma el palíndromo más largo que comienza en la ubicación actual. Por ejemplo, si , generará ( 121 ) ( 33 ) ( 1 ) ( 2 ) , mientras que la cobertura óptima es ( 1 ) ( 213312 ) .w=1213312(121)(33)(1)(2)(1)(213312)

¿El algoritmo codicioso proporciona una aproximación 2 para el problema?

Dean R
fuente

Respuestas: