Ridwan, Tracy Filbert (2015) Desain Dan Analisis Algoritma Multiple String Matching Pada Penyelesaian Problem SPOJ Klasik 12713. Undergraduate thesis, Institut Technology Sepuluh Nopember.
Preview |
Text
5111100176-Undergraduate Thesis.pdf - Published Version Download (2MB) | Preview |
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 > 55201-(S1) Undergraduate Thesis |
| 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 |