Algoritme Knuth-Morris-Pratt

Perhitungan penggeseran pada algoritme ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan formula_1, kita bisa menganggap ketidakcocokan pertama terjadi di antara formula_2 dan formula_3, dengan formula_4. Berarti, formula_5 dan formula_6 tidak sama dengan formula_7. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan formula_8 dari pattern akan sama dengan sebagian akhiran formula_9 dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan formula_8 tersebut sejajar dengan akhiran dari formula_9.