Masalah pencocokan untai terbagi menjadi dua yakni pencocokan untai eksak dan hampiran. Pada skripsi ini, masalah pencocokan untai yang dibahas adalah pencocokan untai eksak. Inti dari masalah pencocokan untai eksak adalah mencari semua posisi kemunculan suatu untai pada untai yang lain. Salah satu ukuran yang membedakan dua buah untai adalah jarak Hamming. Jika diberikan dua buah untai, misalkan x dan y dengan panjang yang sama, maka jarak Hamming antara keduanya adalah banyaknya karakter pada untai x yang berbeda dengan karakter pada untai y pada posisi yang bersesuaian. Dalam pencocokan untai eksak, panjang untai yang akan dicocokan tidak akan selalu sama sehingga jarak Hamming antara keduanya tidak dapat dihitung. Dengan merangkaikan sejumlah untai hampa pada untai yang lebih pendek sehingga panjangnya menjadi sama, jarak Hamming antara keduanya barulah dapat dihitung. Dengan pemikiran inilah akhirnya ukuran jarak Hamming digunakan dalam pencocokan untai eksak untuk mencari semua posisi kemunculan suatu untai pada untai lain yang lebih panjang.
String matching problem is divided into exact and approximate string matching. In this thesis, we discuss the exact string matching. The main problem of exact string matching is to find all position of a string in other string. The measure that used in this thesis is Hamming distance. Given two strings namely the x and y with the equal length, Hamming distance of the two is the number of positions at which the corresponding characters are different. In string matching problem, Hamming distance between them can?t always be calculated because the strings are not always have the same length. By concating a number of empty string with shortest string until the length to be same, then Hamming distance could be calculated. Finally, Hamming distance measure is used by exact string matching to find all position of a string in other string. |
