Algoritme Knuth-Morris-Pratt

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-formula_12 dari pattern. Tabel itu harus memuat formula_13 yang merupakan posisi karakter formula_3 setelah digeser, sehingga kita bisa menggeser pattern sebesar formula_15 relatif terhadap teks.