Subsekuens Sama Terpanjang

Subsekuens mempertahankan karakter dalam urutan yang sama, tetapi boleh melewati beberapa karakter. Dari 'abcde' Anda dapat mengambil 'ace', tetapi tidak pernah 'aec'.

Diberikan dua teks, subsekuens umum terpanjang adalah urutan terpanjang yang muncul pada keduanya dalam urutan relatif yang sama.

Bandingkan prefiks dari kedua teks. Sebuah tabel dua dimensi berdasarkan panjang keduanya mengubah masalah ini menjadi DP kisi yang sudah familier.

Misalkan dp[i][j] adalah panjang LCS dari i karakter pertama A dan j karakter pertama B.

Jika A[i-1] sama dengan B[j-1], huruf yang sama tersebut memperpanjang LCS. Tambahkan satu ke nilai diagonal dp[i-1][j-1].

Jika hurufnya berbeda, abaikan satu karakter dari salah satu teks dan pertahankan hasil yang lebih baik. Ambil nilai maksimum dari dua tetangga.

Prefiks kosong tidak memiliki kesamaan apa pun, sehingga panjang LCS adalah nol. Baris 0 dan kolom 0 tetap berisi nol seluruhnya.

Membuat tabel berukuran n+1 kali m+1 memberikan batas nol secara cuma-cuma. Dengan begitu, pemeriksaan batas yang mengganggu di tepi dapat dihilangkan.

Lakukan perulangan i dan j mulai dari 1 ke atas. Setiap sel hanya membutuhkan nilai di atas, kiri, dan diagonal, yang sudah dihitung.

Panjang LCS lengkap berada di sudut. Jawabannya adalah dp[n][m] setelah setiap sel terisi.

Anda mengakses setiap sel sekali, sehingga pekerjaannya membutuhkan waktu dan memori O(n kali m). Ini cukup untuk menangani teks sepanjang beberapa ribu karakter.

Karakter saat ini, A[i-1] dan B[j-1], sama. Pembaruan mana yang benar?

Buat tabel berukuran n+1 kali m+1: jika cocok, tambahkan satu ke diagonal; jika tidak, ambil tetangga maksimum. Sudut menyimpan panjangnya. 🔗