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:

Untuk mengetahui prinsip kerja dasarnya dapat dilihat di video sederhana berikut. Sekian semoga bermanfaat.

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s