Desain Dan Analisis Algoritma Multiple String Matching Pada Penyelesaian Problem SPOJ Klasik 12713

Ridwan, Tracy Filbert (2015) Desain Dan Analisis Algoritma Multiple String Matching Pada Penyelesaian Problem SPOJ Klasik 12713. Undergraduate thesis, Institut Technology Sepuluh Nopember.

[img] Text
5111100176-Undergraduate Thesis.pdf - Published Version

Download (2MB)

Abstract

String Matching adalah permasalahan klasik tentang pencocokan dua buah string dikatakan sama atau apakah sebuah string merupakan substring dari string lainnya. Permasalahan ini sering dijumpai dalam pencarian kata dalam kamus, pencarian kata dalam suatu dokumen, dan perhitungan DNA. Dalam penelitian ini akan mengimplementasikan struktur data Suffix Array yang dilengkapi dengan informasi Longest Common Prefix untuk menyelesaikan permasalahan String Matching. Struktur data Suffix Array dipilih karena memiliki kompleksitas waktu pembuatan linear dan kompleksitas memori linear. Pada permasalahan String matching terkadang mempunyai suatu syarat khusus dalam proses pencariannya sebagai contoh string tersebut harus identik dan string tersebut harus berulang sebanyak k kali, sehingga harus dilakukan perhitungan tambahan untuk memenuhi syarat khusus tersebut. Pada penelitian ini struktur data suffix array akan dipakai untuk menyelesaikan proses pencarian substring yang berulang tepat sebanyak k kali pada suatu string yang diberikan. ========================================================================================================= String Matching is a classic problem about finding if two string is identic or checking if a string is a substring from the another string. We can see this kind problem when we want to try finding a word from a dictionary, finding a word in a document, or calculation process in DNA. In this final test will try to implement a data structure called suffix array with an extra information about it's longest common prefix for solving string matching problem. Suffix Array is chosen because it's have linear time complexity to build and linear memory complexity. In string matching problem we often face another conditional to fulfil in the searching process for example the string must be identical, and the string must repeated exactly at k times, so another process must be calculated to fulfil that extra condition. In This final test Suffix Array used to solve searching process about finding substring that repeated exactly k times in some string given

Item Type: Thesis (Undergraduate)
Additional Information: RSIf 006.746 Rid d
Uncontrolled Keywords: String Matching, Suffix Array, Longest Common Prefix.
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP
T Technology > T Technology (General) > T57.5 Data Processing
Divisions: Faculty of Information Technology > Informatics Engineering > (S1) Undergraduate Theses
Depositing User: Mr. Tondo Indra Nyata
Date Deposited: 15 May 2019 01:48
Last Modified: 15 May 2019 01:48
URI: http://repository.its.ac.id/id/eprint/63027

Actions (login required)

View Item View Item