Pembahasan Soal Multipalindrom
Kita mendefinisikan suatu fungsi rekursif
JP(Xj) yang menyatakan jumlah minimal palindrom
dari string Xj = substring(1,j) dari string masukan,
untuk j dari 1 s.d panjang string.
Untuk menyederhanakan pendefinisiannya
kita perlu menggunakan notasi Yij untuk menyatakan
substring(i+1,j) dari string masukan (i.e, Xj = concate(Xi, Yij)).
Selanjutnya fungsi itu didefinisikan sbb.
Jika Xj palindrom maka
JP(Xj) = 1.
Jika bukan maka
JP(Xj) = min{JP(Xi) + 1, untuk semua 1 <= i < j dan Yij palindrom}.
Dalam implementasinya kita perlu menghindari penghitungan
berulang JP(Xi). Oleh sebab itu a'la dynamic programming, kita
gunakan tabel JP yang diisi mulai dari j=1, 2, dst.
Kita coba untuk string masukan 'minimisasi'.
Untuk j=1 (X1='m') X1 adalah palindrom, sehingga JP(X1) = 1.
untuk j=2 (X2='mi') JP(X2) = min{JP(X1)+1} = 1+1 =2
untuk j=3 (X3='min') JP(X3) = min{JP(X2)+1} = 2+1 =3
untuk j=4 (X4='mini') JP(X4) = min{JP(X1)+1, JP(X3)+1} = min{2,4} =2
untuk j=5 (X5='minim') X5 adalah palindrom sehingga JP(X5) = 1
untuk j=6 (X6='minimi') JP(X6) = min{JP(X3)+1, JP(X5)+1} = min{4,2} =2
...
dst. sehingga menghasilkan tabel JP(Xj) sebagai berikut:
| j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| Xj |
m |
mi |
min |
mini |
minim |
minimi |
minimis |
minimisa |
minimisas |
minimisasi |
| JP(Xj) |
1 |
2 |
3 |
2 |
1 |
2 |
3 |
4 |
3 |
2 |
Jawaban soal ini adalah JP(X=string masukan) = 2.
Algoritma secara dynamic programming ini bekerja antara O(n2)
dan O(n3).
dimana n adalah panjang string.
(Seandainya tanpa DP??? Hitung sendiri deh...)