String Matching

String Matching atau pencocokan string adalah sebuah metode untuk mencari suatu string. Implementasi sederhana dari String Matching adalah search engine seperti Yahoo atau Google.

            String Matching sendiri merupakan masalah yang sering ditemui dalam dunia peng-codingan, berbagai cara yang telah diterapkan untuk menyelesaikan permasalahan ini diantaranya Algoritma Staightforward Matching, Finite Automata dan Knuth-Morris-Pratt.

            Dalam pencarian string masalah yang didapatkan adalah untuk mencari sebuah string yang terdiri dari beberapa karakter dalam sejumlah besar text. Pencarian String dapat juga digunakan dalam mencari pola bit dalam sebuah file binary.

1.      Algoritma Staightforward Matching

Proses kerja Algoritma Staightforward Matching berawal dari pembadingan karakter pertama dalam string dengan karakter pertama dari text. Apabila kedua karakter tersebut sama maka bandingkan kembali dengan karakter selanjutnya (pindahkan ke karakter selanjutnya) sampai pencocokan keseluruhan string atau menemukan karakter yang tidak sama. Jika ditemukan karakter yang tidak sama maka pindahkan atau gerakan satu langkah kedepan dan akan memualai kembali pencocokan string dari awal.

Dalam kasus terburuk setiap perbandingan karakter telah sukses kecuali dalam pada karakter terakhir string. Dalam kasus ini diperlukan S*(T-S+1) kali perbandingan dengan S melambangkan panjang dalam string dan T melambangkan panjang dalam text.

Algoritma ini terbukti tidak efisien bila digunakan mencari sebuah string dalam text yang sangat panjang karena algoritma ini membandingkan karakter demi karakter sampai karakter yang dibandingkan sesuai.

2.      Algoritma Finite Automata

Finite Automata merupakan algoritma yang memutuskan apakah sebuah kata atau string adalah kata yang diterima oleh mesin automata tersebut. Sebuah automata memiliki status dan fungsi transisi yang merubah status berdasarkan status saat ini dan karakter yang dibaca saat ini. Dalam hal ini ada yang disebut sebagai status akhir dan status ini mungkin lebih dari satu. Bila string tersebut dijalankan dan berakhir di salah satu status akhir maka string tersebut diterima.

Finite Automata juga dapat digunakan untuk menerima string yang dicari dan jika ditemukan sebuah kata yang berarkhir di status akhir finite automata dibuat maka itu merupakan string yang dicari.

Kelebihan dari finite automata adalah bisa menetukan status mana yang akan dituju setelah sebuah status menerima sebuah karakter.

3.      Algoritma Knuth-Morris-Pratt

Algoritma Knuth-Morris-Pratt (KMP) memiliki pemikiran dasar dari Algoritma Finite Automata dimana untuk setiap karakter yang dibandingkan akan diputuskan berhasil atau gagal.

Prinsip dari Algoritma KMP adalah membangun sebuah mesin automata yang status-statusnya merupakan status dari string yang yang dicari dan setiap status memiliki kondisi berhasil dan gagal. Kondisi berhasil berarti status akan bergerak mendekat ke status akhir dan kondisi gagal artinya status bisa jadi semakin jauh atau tetap terhadap status akhir.