Algoritma Knuth-Morris-Pratt: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Menghilangkan spasi sebelum tanda koma dan tanda titik dua |
k →Cara kerja: pembersihan kosmetika dasar |
||
| (2 revisi perantara oleh 2 pengguna tidak ditampilkan) | |||
Baris 1:
'''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,
Jika kita melihat [[Algoritme pencarian string#Algoritme brute force dalam pencarian string|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.<ref>{{en}}Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5</ref>
Baris 6:
Perhitungan penggeseran pada algoritme 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 di 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]</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.
Secara sistematis, langkah-langkah yang dilakukan algoritme Knuth-Morris-Pratt pada saat mencocokkan string:
| |||