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.

Penulis: rahmadya

I'm a simple man .. Lahir di Sleman Yogyakarta, 7 Juni 1976 TK : - (tidak ada TK di tj Priok waktu itu) SDN : Papanggo, Jakarta 83 - 89 SMPN : 129, Jakarta 89 - 92 SMAN : 8, Yogyakarta 92 - 95 Univ. : Fak. Teknik UGM, Yogyakarta 95 - 2001 Pasca. : Tek. Informatika STMIK Nusa Mandiri, Jakarta 2008 - 2010 Doctoral : Information Management Asian Institute of Technology, Thailand 2013 - 2018 Pekerjaan: Tek. Komputer AMIK BSI Jakarta : 2002 - 2005 IT Danamon Jakarta : 2005 - 2008 Tek. Informatika STMIK Nusa Mandiri Jakarta : 2005 - 2008 Univ. Darma Persada : 2008 - Skrg Fakultas Teknik Universitas Islam "45" Bekasi : 2008 - Skrg ( Homebase)

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.