Menutupi string oleh palindrom

Diberikan string , penutup palindrom adalah urutan p 1 p 2 ⋯ p m dari kata p i sedemikian rupa sehingga p 1 p 2 ⋯ p m = w dan sedemikian rupa sehingga setiap p i adalah palindrom .$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$

Seberapa sulit untuk menemukan ukuran penutup palindrome minimal? (ini tampaknya bisa dilakukan dengan pemrograman dinamis, tapi saya tidak yakin itu berfungsi).

Apakah masalah menjadi lebih sulit jika diberikan sebagai input juga terikat pada setiap panjang palindrom?$b$

Pertimbangkan algoritma serakah sederhana, yang selalu mengambil palindrom terpanjang yang dimulai pada lokasi saat ini. Sebagai contoh, jika , maka akan keluaran ( 121 ) ⋅ ( 33 ) ⋅ ( 1 ) ⋅ ( 2 ) , sedangkan penutup optimal adalah ( 1 ) ⋅ ( 213.312 ) .$w=1213312$$(121)\cdot(33)\cdot(1)\cdot(2)$$(1)\cdot(213312)$

Apakah algoritma serakah memberikan 2 perkiraan untuk masalah?

$O(n \log n)$

Algoritma subquadratic untuk faktorisasi palindrome minimum oleh Fici et al

EERTREE: Struktur Data yang Efisien untuk Memproses Palindrom di String oleh Rubinchik dan Shur.