Perancangan dan Analisis Penerapan Algoritma Z dan Pemrograman Dinamis pada Persoalan Penghitungan Konfigurasi Substring: Studi Kasus SPOJ 37443 – ACRYM II

Megananda, Graidy (2024) Perancangan dan Analisis Penerapan Algoritma Z dan Pemrograman Dinamis pada Persoalan Penghitungan Konfigurasi Substring: Studi Kasus SPOJ 37443 – ACRYM II. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201188-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (3MB) | Request a copy

Abstract

Akronim merupakan kata yang dibentuk dari huruf awal atau prefiks pada kata dalam suatu frasa. Jika diketahui dalam setiap T kasus uji terdapat suatu akronim A dan frasa yang terdiri dari N string: W_1,W_2…,W_n, maka terdapat banyak cara untuk menyusun akronim tersebut tergantung dari jenis string setiap W_i–suatu kata, konjungsi, atau adposisi–dan seberapa panjang prefiks setiap W_i digunakan. Berdasarkan pernyataan tersebut, permasalahan ini dapat dikategorikan ke dalam permasalahan kombinatorik. Namun, solusi yang digunakan justru berbasis rekuren dan tidak didekati dengan solusi kombinatorik. Dalam tugas akhir ini, dilakukan analisis, desain, dan implementasi solusi permasalahan tersebut.
Tugas akhir ini mengacu pada perancangan dan penerapan algoritma Z dengan pendekatan pemrograman dinamis dalam mencari banyaknya konfigurasi substring dari masukan N string yang mungkin untuk membentuk akronim yang diberikan. Algoritma Z digunakan untuk mencari kemunculan prefiks dari setiap string W_i pada akronim A dan menyimpannya ke dalam array Z. Sedangkan, pendekatan pemrograman dinamis digunakan karena solusi yang dapat memenuhi adalah yang mengikuti pendekatan divide and conquer.
Berdasarkan hasil uji coba pada studi kasus yang diberikan, solusi pendekatan Dynamic Programming menempati peringkat pertama dengan waktu rata-rata 5,47 detik dan memori rata-rata 5,2 MB. Tugas akhir ini menghasilkan algoritma penghitungan banyaknya konfigurasi substring dari masukan N string yang mungkin untuk membentuk akronim yang diberikan dan diharapkan dapat memberikan kontribusi pada perkembangan ilmu pengetahuan dan teknologi informasi.
===============================================================================================================================
An acronym is made up of the initial letter(s) or a prefix of the words in a phrase. Suppose there are T test cases, and for each test case, there's an acronym A and a phrase consisting of N strings: W_1,W_2…,W_n. In this case, there can be multiple ways to construct the given acronym, depending on the type of string each W_i represents—whether it's a word, conjunction, or adposition—and how long the prefix of each W_i is used. Based on this statement, the problem could be categorized in the combinatory category. However, the proposed solution is based on recursion rather than combinatorial solutions. This final project discuss the analysis, design, and implementation of the solution for the given problem.
This final project refers to the design and implementation of Z-algorithms with a dynamic programming approach to find all valid substring configurations from N string to construct the given acronym. The Z-algorithm is used to identify all occurrences of prefixes for each W_i in the given acronym A and store them in the Z-array. On the other hand, the dynamic programming approach is used due to the fact that a valid solution is achieved by following the divide and conquer approach.
Based on the test results of the given case study, the Dynamic Programming approach solution ranks first with an average time of 5.47 seconds and an average memory of 5.2 MB. This final project produces an algorithm for calculating the number of possible substring configurations from N strings to form the given acronym, with the aim of contributing to the advancement of science and information technology.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Akronim, Algoritma Z, Pemrograman Dinamis, Pencocokan Pola, Pencocokan String, Prefiks String, Acronym, Dynamic Programming, Pattern Matching, String Matching, String Prefix, Z-Algorithm
Subjects:	Q Science Q Science > QA Mathematics > QA159 Algebra Q Science > QA Mathematics > QA184 Algebra, Linear 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:	Graidy Megananda
Date Deposited:	26 Jul 2024 04:22
Last Modified:	26 Jul 2024 04:23
URI:	http://repository.its.ac.id/id/eprint/109048

Actions (login required)

View Item