Algoritma LCS dan Teman-teman

Si Longest Common Subsequence (LCS) dan teman-teman memang berhasil buat kepala muter-muter whehehe,, LCS dan teman-teman menambah asik mata kuliah Desain Analisis dan Algoritma ^________^,, sebenarnya jika dipelajari benar-benar kita bisa paham sih, dasar saya yang malas kali ya -_-. Padahal Dosen dah Ngasi buku Introduction to Algorithms (karangan om Thomas H. Cormen dkk) trus teman dah ngasi buku kunci jawaban buku om Thomas H. Cormen. Berikut contoh lcs di buku om cormen, silahkan download bukunya, semoga kalian bisa lebih memahami si LCS dan teman-teman. Berikut salah satu contoh yang ada di buku om cormen.

lcs

lcs

Algoritma menghitung panjang LCS

LCS-Length(X,Y)

1.   m ß length [X]

2.   n ß length [Y]

3.   For iß1 to m do c[i,0] ß 0

4.   For j ß 0 to n do

5.   c[0,j] ß 0

6.   For i ß 1 to m do

7.          for j ß 1 to n do

8.                if xi = yj then c[i,j] ß c[i-1,j-1]+1

9.                                       b[i,j]ß “  ã   “

10.                                                else if  c[i-1, j]   ≥ c[i, j-1]

11.                                                         then  b[i, j] ß “ á”

12.                                                         else c[i, j] ← c[ i, j-1]

13.                                                                 b[I,j] ß “ ← “

14.                     Return c  and b

 

Download:

Buku Introduction to Algoritma by Thomas H. Cormen

Buku penyelesaian soal-soal yang ada di buku Introduction to Algoritma by Thomas H. Cormen

2 thoughts on “Algoritma LCS dan Teman-teman

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s