Akbar, Rahmat Faris (2024) Perancangan Dan Analisis Penerapan Algoritma LCS Consecutive Suffix Alignment Landau - Myers - Ziv-Ukelson Dengan Pendekatan Next Match: Studi Kasus SPOJ 226 JEWELS - Jewelry And Fashion. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5025201003-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5025201003-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (3MB) | Request a copy |
Abstract
Subsequence dari sebuah string adalah sembarang string yang dihasilkan dari penghapusan nol atau lebih karakter penyusun string tersebut. Longest Common Subsequence (LCS) merupakan subsequence terpanjang yang sama antara dua buah string. Permasalahan “JEWELS - Jewelry and Fashion” pada situs penilaian Sphere Online Judge (SPOJ) berfokus pada pencarian nilai panjang LCS maksimum dengan posisi titik pemotongan terkecil yang bisa didapatkan dari seluruh kemungkinan pemotongan sebuah string N yang akan dipotong menjadi dua bagian, direpresentasikan sebagai string A dan string B dengan mempertimbangkan rotasi 180 derajat. Dalam banyak kasus, pendekatan tradisional dalam menghitung LCS dengan pemrograman dinamis mengalami keterbatasan dalam efisiensi waktu, terutama pada kasus dengan panjang string yang sangat besar. Pada Tugas Akhir ini, untuk meningkatkan efisiensi, akan digunakan algoritma LCS Consecutive Suffix Alignment Landau - Myers - Ziv-Ukelson dengan pendekatan Next Match. Berdasarkan hasil uji coba yang telah dilakukan pada studi kasus SPOJ 226 JEWELS - Jewelry and Fashion, solusi kode sumber program mendapatkan hasil accepted pada situs penilaian SPOJ dengan rata-rata waktu yang dibutuhkan adalah selama 5,168 detik dan memori rata-rata sebesar 857 MB. Hasil dari Tugas Akhir ini diharapkan dapat memberikan kontribusi pada perkembangan ilmu pengetahuan dan teknologi informasi khususnya dalam topik pattern matching dan pemrograman dinamis.
===================================================================================================================================
A subsequence of a string is any string that can be generated by deleting zero or more characters from the original string. The Longest Common Subsequence (LCS) is the longest sequence that appears in the same order within two strings. The problem "JEWELS - Jewelry and Fashion" on the Sphere Online Judge (SPOJ) site focuses on finding the maximum LCS (Longest Common Subsequence) length with the smallest cutting point position that can be obtained from all possible cuttings of a string N, which is to be cut into two parts, represented as string A and string B, considering a 180-degree rotation. Traditional approaches to calculating LCS using dynamic programming often face efficiency limitations, especially with very large strings. In this thesis, to enhance efficiency, the LCS Consecutive Suffix Alignment Landau - Myers - Ziv-Ukelson algorithm with the Next Match approach is employed. Based on experiments conducted on the SPOJ 226 JEWELS - Jewelry and Fashion case study, the program's source code achieved an accepted result on the SPOJ platform, with an average runtime of 5.168 seconds and an average memory usage of 857 MB. The results of this thesis are expected to contribute to the advancement of knowledge and information technology, particularly in the fields of pattern matching and dynamic programming.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | Consecutive Suffix Alignment, Longest Common Subsequence, Pattern Matching, Pemrograman Dinamis, Consecutive Suffix Alignment, Dynamic Programming, Longest Common Subsequence, Pattern Matching. |
| Subjects: | Q Science > QA Mathematics > QA401 Mathematical models. Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Rahmat Faris Akbar |
| Date Deposited: | 30 Jul 2024 04:25 |
| Last Modified: | 30 Jul 2024 04:25 |
| URI: | http://repository.its.ac.id/id/eprint/109386 |
Actions (login required)
 |
View Item |