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.

1)m  : 01 23 456 7 8901 23 4 567 89 01 2
   S   : ABC   ABCDAB  ABCDABCDABDE
   W : ABCDABD
    i   : 0 1 23 45 6

Ket : dari proses pertama ini bisa diketahui bahwa huruf D dari kata yang dicari tidak sama dengan karakter spasi, maka diproses selanjutnya pencocokkan akan dimulai dari kata kedua setelah spasi, sebab karakter spasi tidak mungkin menjadi awalan dari kata yang dicari yaitu ABCDABD.

2)m : 01 2345 67 8901 23 45 67 89 01 2
    S  : ABC  ABCDAB  ABCDABCDABDE
   W :           ABCDABD
    i   :           0 1 23 45 6

Ket : dari proses kedua ini kata yang dicari masih belum sepenuhnya cocok, maka proses dilanjutkan dengan ke karakter berikutnya yang masih mungkin cocok.

3)m : 01 2345 67 890  12 345 67 89 01 2
    S  : ABC  ABCDAB   ABCDABCDABDE
   W :                       ABCDABD
    i   :                       0 1 23 45 6

Ket : proses pencocokkan kata masih gagal atau tidak memenuhi kriteria kata yang dicari.

4)m : 01 2345 67 890  12 345 67 89 01 2
    S  : ABC  ABCDAB   ABCDABCDABDE
   W :                               ABCDABD
    i   :                               0 1 23 45 6

Ket : proses pencarian sekali lagi menunjukkan bahwa kata yang dicari belum semuanya cocok dengan string yang diberikan.

5)m : 01 2345 67 890  12 345 67 89 01 2
    S  : ABC  ABCDAB   ABCDABCDABDE
   W :                                           ABCDABD
    i   :                                           0 1 23 45 6

Ket : pada langkah kelima ini semua karakter atau huruf dalam kata yang dicari menemui padanannya pada kalimat atau string yang diberikan, maka proses berhenti dengan mengembalikan posisi dimana kata ditemukan.

Dalam contoh diatas m merupakan index dari kata dalam kalimat yang dicari, S adalah kalimat dimana kata akan dicari, W adalah kata yang akan dicari dalam S, dan i adalah index dari W.
Berikut ini saya berikan source program lengkap dalam bahasa C yang saya buat berdasarkan cara kerja algoritma diatas.



#include<string.h>
#include<constream.h>
#include<stdlib.h>

int errtime=0;

void KMP(int ctrs,int ctrw,char s[],char w[],int &posketemu,int tctrs)
{if(ctrw>strlen(w)-1) //cek sdh sampai char dicari terakhir
{posketemu=ctrs-ctrw;} //maka sudah ketemu
else //jika tidak ketemu
{if(w[ctrw]==s[ctrs]) //bandingkan kar yg dicari(w[ctrw]) dgn s[ctrs]
{ctrw++; ctrs++; tctrs++;} //jika ketemu increment indek keduanya
else
{ctrw=0; // kalau tdk ketemu, jika index ctrw>0
if(s[ctrs]==' '){ctrs++; tctrs++;} //jika salah dan char " " langsung inc(ctrs);
else
{if(errtime==0)
{if(ctrs<2) ctrs="=" errtime="0;" poskata="0;">>w;
if((strncmp(s," ",strlen(s))!=0)&(strncmp(w," ",strlen(w))!=0))
{KMP(0,0,s,w,poskata,0);
if(poskata>=0)
{itoa(poskata,tpos,10);
cetak<<setxy(1,3)<<"kata ketemu di posisi :"<<tpos; getch(); }else {cetak<<setxy(1,3)<<"kata tidak ketemu dalam kalimat"; getch(); } } }