“Longest Common Subsequence is the problem of finding the longest common subsequence of two sequences of items. This is used in the “diff” file comparison utility”.
Longest Common Subsequence adalah sebuah masalah untuk mencari dan mendapatkan subsequence umum yang terpanjang dari 2 sequence.
Misalnya saja ada dua rangkaian : x {a,b,c,d,e} dan y{d,e,f,g}. Subsequence adalah himpunan baru yang dapat di bentuk dari rangkaian tersebut dengan syarat anggota dari himpunan yang baru merupakan anggota dari himpunan yang awal dan disusun berurutan. Subsequence dari x misalnya {a}{b,d}{a,c,e} sedangkan subsequence dari y misalnya{d}{d,e}{d,f,g}. Sedangkan untuk common subsequence adalah subsequence yang sama dari kedua himpunan tersebut misalnya saja {d},{d,e} Longest common subsequence (LCS) adalah sebuah rangkaian elemen dimana elemen dari rangkaian tersebut adalah elemen yang sama dari beberapa rangkaian yang lain yang disusun berurutan LCS dari dua rangkain tersebut {d,e}.
Untuk mendapatkan the longest common subsequence, ada 3 cara yang bisa dipakai yaitu, iteratif dengan bantuan, iteratif tanpa bantuan dan rekursif. Kali ini, yang dibahas adalah cara rekursif. Jika terdapat X dengan elemen X1, X2, X3, …, Xm. Dan terdapat Y dengan elemen Y1, Y2, Y3, …, Yn. Maka, dapat dibentuk LCSnya yaitu Z dengan elemen Z1, Z2, Z3, …, Zk.
Filed under: Uncategorized Tagged: | implementasi LCS, LCS, pencarian lokasi
