Algoritma Knuth-Morris-Pratt: Perbedaan antara revisi

Algoritma'''Algoritme Knuth-Morris-Pratt''' adalah salah satu [[algoritme pencarian string]], dikembangkan secara terpisah oleh [[Donald Knuth|Donald E. Knuth]] pada tahun 1967 dan [[James Morris|James H. Morris]] bersama [[Vaughan Pratt|Vaughan R. Pratt]] pada tahun 1966, namuntetapi keduanya mempublikasikannya secara bersamaan pada tahun 1977.

Jika kita melihat algoritma[[Algoritme pencarian string#Algoritme brute force dalam pencarian string|algoritme brute force]] lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnyassebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.<ref>{{en}}Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5</ref>

Perhitungan penggeseran pada algoritmaalgoritme ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan <math>teks[i..i+n-1]</math>, kita bisa menganggap ketidakcocokan pertama terjadi diantaradi antara <math>teks[i+j]</math> dan <math>pattern[j]</math>, dengan <math>0 < j < n</math>. Berarti, <math>teks[i..i+j-1] = pattern[0..j-1]</math> dan <math>a=teks[i+j]≠b</math> tidak sama dengan <math>b=pattern[j]</math>. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan <math>v</math> dari pattern akan sama dengan sebagian akhiran <math>u</math> dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan <math>v</math> tersebut sejajar dengan akhiran dari <math>u</math>.

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-<math>j</math> dari pattern. Tabel itu harus memuat <math>next[j]</math> yang merupakan posisi karakter <math>pattern[j]</math> setelah digeser, sehingga kita bisa menggeser pattern sebesar <math>j-next[j]</math> relatif terhadap teks.<ref>{{en}} Knuth, Donald E. Morris, James H. Pratt, Vaughan R. 1977. Fast Pattern Matching in Strings, SIAM Journal of Computing Vol 6 No.2.</ref>

Secara sistematis, langkah-langkah yang dilakukan algoritmaalgoritme Knuth-Morris-Pratt pada saat mencocokkan string:

# AlgoritmaAlgoritme Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.

# Dari kiri ke kanan, algoritmaalgoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

## Semua karakter di pattern cocok. Kemudian algoritmaalgoritme akan memberitahukan penemuan di posisi ini.

# AlgoritmaAlgoritme kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.