Algoritma Knuth-Morris-Pratt

Algoritma Knuth-Morris-Pratt adalah salah satu algoritme pencarian string, dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966, tetapi keduanya memublikasikannya secara bersamaan pada tahun 1977.

Jika kita melihat algoritme brute force lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5

 Cara kerja 
Perhitungan penggeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan , kita bisa menganggap ketidakcocokan pertama terjadi di antara  dan , dengan . Berarti,  dan  tidak sama dengan . Ketika kita menggeser, sangat beralasan bila ada sebuah awalan  dari pattern akan sama dengan sebagian akhiran  dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan  tersebut sejajar dengan akhiran dari .

Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokkan di karakter ke- dari pattern. Tabel itu harus memuat  yang merupakan posisi karakter  setelah digeser, sehingga kita bisa menggeser pattern sebesar  relatif terhadap teks. Knuth, Donald E. Morris, James H. Pratt, Vaughan R. 1977. Fast Pattern Matching in Strings, SIAM Journal of Computing Vol 6 No.2.

Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string:
 Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.
 Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
 Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
 Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
 Algoritma kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

 Pseudocode 
Berikut adalah pseudocode algoritma KMP pada fase pra-pencarian:
 procedure preKMP(
     input P: array[0..n-1] of char,
     input n: integer,
     input/output kmpNext: array[0..n] of integer
 )
 Deklarasi:
 i,j: integer

 Algoritma
   i:= 0;
   j:= kmpNext[0]:= -1;
   while (i < n) {
      while (j > -1 and not(P[i] = P[j]))
         j:= kmpNext[j];
      i:= i+1;
      j:= j+1;
      if (P[i] = P[j])
         kmpNext[i]:= kmpNext[j];
      else
         kmpNext[i]:= j;
      endif
   endwhile

Dan berikut adalah pseudocode algoritma KMP pada fase pencarian:
 procedure KMPSearch(
     input m, n: integer,
     input P: array[0..n-1] of char,
     input T: array[0..m-1] of char,
     output ketemu: array[0..m-1] of boolean
 )

 Deklarasi:
 i, j,next: integer 
 kmpNext: array[0..n] of interger

 Algoritma:
 preKMP(n, P, kmpNext) 
 i:=0
 while (i<= m-n) do
     j:=0
     while (j < n and T[i+j] = P[j]) do 
        j:=j+1
     endwhile
     if(j >= n) then
        ketemu[i]:=true;
     endif
     next:= j - kmpNext[j]
     i:= i+next
 endwhile

 Kompleksitas 
Algoritma ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritma ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alpabet

 Referensi 

 Lihat pula 
 Daftar algoritme
 Algoritme pencarian string
 Algoritme Boyer-Moore

 Pranala luar 
 Halaman berisi penjelasan tentang algoritma Knuth-Morris-Pratt dan juga sebuah applet yang menganimasikan cara kerjanya

Kategori:Algoritme pencarian
Kategori:Algoritme string