Ahli120 XPUnit 13: Pemrograman Dinamis, soal 8 dari 10
Kesamaan Dua Teks
Hitung panjang subbarisan bersama terpanjang dari dua teks.
Program pendeteksi kemiripan tugas membandingkan dua teks dengan mencari subbarisan bersama terpanjang (LCS). Subbarisan diambil dengan membuang sebagian huruf tanpa mengubah urutan sisanya. LCS dari dinamis dan diagram adalah diam, panjangnya 4.
Masukan
Dua baris, masing-masing berisi 1 sampai 500 huruf kecil.
Keluaran
Panjang subbarisan bersama terpanjang.
Contoh masukan dan keluaran
Contoh 1
Masukan
dinamis diagram
Keluaran
4
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Misalkan L[i][j] adalah panjang LCS dari i huruf pertama teks A dan j huruf pertama teks B.
Petunjuk 2
Bila huruf ke-i dan ke-j sama, L[i][j] = L[i-1][j-1] + 1. Selain itu, ambil yang lebih besar antara L[i-1][j] dan L[i][j-1].