Perancangan dan Penerapan Struktur Data Trie dan Suffix Automata sebagai Metode Penyelesaian Permasalahan Pencocokan String pada Studi Kasus Spoj Count an a Trie (COT4)

Laksana, Bayu (2021) Perancangan dan Penerapan Struktur Data Trie dan Suffix Automata sebagai Metode Penyelesaian Permasalahan Pencocokan String pada Studi Kasus Spoj Count an a Trie (COT4). Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111740000020-Undergraduate__Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (1MB) | Request a copy

Abstract

Permasalahan yang melibatkan string matching atau pencocokan string merupakan permasalahan klasik dalam dunia komputer, yaitu dalam bidang bioinformatika, DNA sequencing, mesin pencari, pengolahan teks, pengenalan pola, lain sebagainya. Tugas akhir ini membahas permasalahan pencocokan string yang terdapat pada situs Sphere Online Judge Count on a Trie. Metode pencocokan string dengan menggunakan bantuan struktur data trie dan suffix automata. Kemudian properti suffix link pada suffix automata untuk membangun segment tree sebagai bantuan dalam melakukan pencocokan string. Dari hasil uji coba, solusi yang diajukan mampu melewati batasan yang ditentukan dari situs Sphere Online Judge dan dapat melakukan pencocokan string dengan efisien. Waktu eksekusi yang dibutuhkan rata-rata adalah 0,85 detik dan memori rata-rata 107 MB.
====================================================================================================
Problems involving string matching are classic problems in the computer world, i.e., in the fields of bioinformatics, DNA sequencing, search engines, text processing, pattern recognition, and so on. This thesis discussed a string matching problem found on the Sphere Online Judge Count on a Trie. The string matching has been done by using the trie and suffix automata data structures. Then, the suffix link property on the suffix automata will be processed to build segment tree(s) as a helper for the string matching. From the testing results, it can be shown that the proposed solution has been able to pass the specified limits on the Sphere Online Judge and could perform string matching efficiently. The average execution time required is 0.85 seconds and the average memory used is 107 MB.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	pencocokan string, segment tree, struktur data, suffix automata, trie, data structure, segment tree, string matching, suffix automata, trie
Subjects:	Q Science > QA Mathematics > QA76.F56 Data structures (Computer science)
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Bayu Laksana
Date Deposited:	02 Aug 2021 07:32
Last Modified:	02 Aug 2021 07:32
URI:	http://repository.its.ac.id/id/eprint/84685

Actions (login required)

View Item