Thursday 31 January 2008

What Is Knuth-Morris-Pratt ?

Bagi yang menyukai bahasan tentang algoritma dan pemrograman harusnya sudah mengetahui salah satu algoritma yang cukup terkenal ini. Baiklah saya beri tahu saja secara singkat Knuth Morris Pratt adalah suatu algoritma pemrograman yang ditemukan bersama-sama oleh Donald Knuth dan Pratt serta Morris secara terpisah pada tahun 1977. Meskipun antara Knuth dan Pratt serta Morris menemukan algoritma secara sendiri-sendiri, namun mereka bertiga sepakat untuk mempublikasikannya secara bersama-sama, maka jadilah nama algoritma ini Knuth-Morris-Pratt.
Algoritma Knuth-Morris-Pratt atau yang sering disingkat KMP ini merupakan salah satu algoritma yang digunakan untuk mencari apakah suatu kata terdapat dalam suatu string atau kumpulan kata. Cara kerja algoritma ini sebenarnya cukup sederhana yakni dengan cara mencocokkan kata yang mau dicari dalam string atau kumpulan kata sampai seluruh huruf dalam kata yang dicari tadi menemui padanannya dalam kumpulan kata yang ada. Jika ada satu saja huruf dari kata yang dicari tidak cocok, maka proses pengecekan akan diulangi seperti semula tapi ke karakter selanjutnya yang masih mungkin bisa sesuai dengan karakter awal dari kata yang dicari. Untuk lebih jelas mengenai cara kerja algoritma ini, perhatikan contoh pergerakan dari proses pencarian kata berikut.

KumpulBlogger