Покрывающая струна палиндромами

12

Дана строка , А палиндром крышка представляет собой последовательность р 1 р 2р м слов р я такое , что р 1 р 2р м = ш , и так , что каждый р я палиндром ,w=σ1σ2σnp1p2pmpip1p2pm=wpi

Насколько сложно найти размер минимального палиндромного покрытия? (это кажется выполнимым динамическим программированием, но я не уверен, что это работает).

Проблема усложняется, если в качестве входных данных задана также граница для каждой длины палиндрома?b

Рассмотрим простой жадный алгоритм, который всегда использует самый длинный палиндром, который начинается с текущего местоположения. Например, если , то будет выведено ( 121 ) ( 33 ) ( 1 ) ( 2 ) , а оптимальное покрытие равно ( 1 ) ( 213312 ) .w=1213312(121)(33)(1)(2)(1)(213312)

Предоставляет ли жадный алгоритм 2-аппроксимацию для задачи?

Дин Р
источник

Ответы: