Algoritma Knuth-Morris-Pratt
Algoritma Knuth-Morris-Pratt, dikembangkan secara terpisah oleh Donald E. Knuth pada tahun dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966, namun keduanya mempublikasikannya secara bersamaan pada tahun 1977.
Jika kita melihat algoritma brute force lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnyas kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.
Cara kerja
Perhitungan penggeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan teks[i..i+n-1], kita bisa menganggap ketidakcocokan pertama terjadi diantara teks[i+j] dan pattern[j], dengan 0 < j < n. Berarti, teks[i..i+j-1] = pattern[0..j-1] dan a=teks[i+j]≠b=pattern[j]. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan v dari pattern akan sama dengan sebagian akhiran u dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan v tersebut sejajar dengan akhiran dari u.
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-j dari pattern. Tabel itu harus memuat next[j] yang merupakan posisi karakter pattern[j] setelah digeser, sehingga kita bisa menggeser pattern sebesar j-next[j] relatif terhadap teks.
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.