Praktek Longest Common Subsequence (LCS) dengan C++ Online

[algoritma|t.informatika|r.408|pert.11]

Longest Common Subsequence (LCS) merupakan rentetan string dari dua string yang dibandingkan. Misalnya string1: a-b-d-a-c-e dan string2: b-a-b-c-e.

Di sini b-a-c-e merupakan LCS. String a tidak boleh dengan a pada string 1 karena berbenturan dengan koneksi b-b antara string 1 dan string 2. Salah satu metode yang efisien adalah dengan pemrograman dinamis dengan cara:

Membuat tabel
Mengekstrak LCS

Tabel berisi arah panah (kiri, atas, atau diagonal) disertai nilai tertentu yang gunanya untuk mengekstrak LCS.

Dari tabel diketahui LCS yang berwarna pink yaitu b-a-c-e.

Implementasi Dalam Bentuk Program

Banyak situs-situs ok yang menyediakan kode sumber untuk algoritma mencari LCS lewat pemrograman dinamis. Untungnya juga banyak situs-situs yang menyediakan compiler beberapa bahasa pemrograman, misalnya bahasa C++. Jadi tidak perlu khawatir jika di komputer tidak terinstal kompiler C++. Bahkan bisa dijalankan lewat handphone. Situs yang jalan untuk kode program sampel berikut adalah onlinegdb. Hapus semua lembar kerjanya (berisi contoh program mengeprint: “hello word”) copy dan paste kode berikut:

Program tersebut mencontohkan mencari LCS dari dua string AGGTAB dan GXTXAYB yang menghasilkan string LCS: GTAB. Tekan tombol RUN dan lihat hasilnya di bagian bawah jendela onlinegdb. Atau ganti dengan contoh di atas Char X[]=”ABDACE” dan Char Y[]=”BABCE” yang hasilnya berikut: