Jelaskan Cara kerja dari Algoritma Knuth-Morris-Pratt

Perhitungan penggeseran pada algoritme 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.

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

Algoritme Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.

Dari kiri ke kanan, algoritme 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 algoritme akan memberitahukan penemuan di posisi ini.

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