Perancangan Dan Analisis Algoritma Incremental Ad Hoc Pada Permasalahan Pencocokan Substring: Studi Kasus SPOJ 41823 - Martia Auris 3020

Kurniawan, Gabrielle Immanuel Osvaldo (2025) Perancangan Dan Analisis Algoritma Incremental Ad Hoc Pada Permasalahan Pencocokan Substring: Studi Kasus SPOJ 41823 - Martia Auris 3020. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211135-Undergraduated_thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2027. Download (11MB) | Request a copy

Abstract

SPOJ (Sphere Online Judge) adalah sebuah platform yang menyediakan sistem evaluasi otomatis untuk solusi lebih dari 4.000 soal, mulai dari tantangan singkat hingga pembelajaran algoritma, sehingga menjadi sarana yang efektif untuk mengasah kemampuan pemrograman. Salah satu soal dalam kategori classical di SPOJ, yaitu "Martia Auris 3020," merupakan masalah pencocokan string yang belum memiliki pembahasan mendetail terkait solusinya. Dalam studi kasus ini, terdapat sebuah kasus superbug yang perlu dicari pada sekuen pasien. Sekuen pasien terdiri dari 2 bagian yaitu sekuen sehat dan sekuan pasien saat ini. Setelah ditemukan kecocokan di sekuen saat ini maka diposisi kecocokan yang sama dicek sekuen yang termutasi. Kompleksitas soal terletak pada beberapa kondisi pencocokan dengan karakter "N", dan “#” yang memerlukan modifikasi pencocokan string. Penyelesaian studi kasus SPOJ 41823 Martia Auris 3020 dirancang dengan menggunakan teknik incremental yang fokus pada pengolahan data secara bertahap. Adapun tahap pengolahan data yang dilakukan meliputi memproses dan mencocokkan pola dalam teks kemudian memetakan posisi kemunculan tersebut ke teks lain. Implementasi solusi yang dikembangkan untuk menyelesaikan studi kasus SPOJ 41823 Martia Auris 3020 telah melalui pengujian kebenaran pada platform SPOJ. Hasil pengujian ini menunjukkan bahwa algoritma berhasil menyelesaikan soal dengan status accepted, dan dengan statistik waktu atau memori terbaik dari 5 user yang menyelesaikan soal ini per desember 2024. Keberhasilan ini menunjukkan bahwa solusi yang diusulkan tidak hanya mampu menyelesaikan masalah secara fungsional, tetapi juga sangat memperhatikan efisiensi dalam hal waktu dan memori, yang merupakan hal krusial dalam platform SPOJ.
=================================================================================================================================
SPOJ (Sphere Online Judge) is a platform that provides an automated evaluation system for solutions to more than 4,000 problems, ranging from quick challenges to algorithmic learning. One of the problems in the classical category on SPOJ, titled "Martia Auris 3020," involves a string matching challenge that has yet to receive a detailed discussion regarding its solution. In this case study, the problem revolves around finding a superbug sequence within a patient’s sequence. The patient’s sequence consists of two parts: the healthy sequence and the current patient sequence. Once a match is found in the current sequence, the same position is checked for mutated sequences. The complexity of the problem lies in the various matching conditions involving the characters "N" and "#," which require modifications to traditional string matching methods. The solution to the SPOJ 41823 Martia Auris 3020 case study was developed utilizing an incremental technique that centers on systematically processing the data in distinct stages. The phases involved are identifying and matching patterns within the given text, followed by mapping the positions of these identified occurrences to a different text. The implementation of the solution developed to solve SPOJ 41823 Martia Auris 3020 has undergone correctness testing on the SPOJ platform. The test results show that the algorithm successfully solved the problem with an "accepted" status, and with the best time and memory statistics out of the five users who solved the problem by december 2024. This success indicates that the proposed solution not only solves the problem functionally but also pays great attention to efficiency in terms of time and memory, which is crucial in SPOJ.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Ad-hoc, Algoritma, Wildcard
Subjects:	Q Science > QA Mathematics > QA141 Numeracy--Problems, exercises, etc. Q Science > QA Mathematics > QA76 Computer software 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:	Gabrielle Immanuel Osvaldo Kurniawan
Date Deposited:	01 Feb 2025 06:59
Last Modified:	01 Feb 2025 06:59
URI:	http://repository.its.ac.id/id/eprint/117250

Actions (login required)

View Item