Algoritma Knuth-Morris-Pratt merupakan algoritma yang membangun sebuah mesin automata dimana dia memiliki status-status yang statusnya itu sendiri merupakan status
dari string yang sedang kita cari. Setiap status memiliki fungsi True (Benar/Berhasil) dan False (Salah/Gagal). Status True artinya status akan bergeser bergerak mendekati status akhir, sebaliknya jika statusnya False maka dia akan semakin jauh atau tetap tidak bergerak dari akhir. Nantinya kita akan mendapatkan sebuah karakter dari text saat kita berhasil dalam proses perbandingan dan akan me-reuse karakter bila kita gagal (Sistemnya hampir mirip dengan Brute-Force). Ilustrasinya Sbb :
dari string yang sedang kita cari. Setiap status memiliki fungsi True (Benar/Berhasil) dan False (Salah/Gagal). Status True artinya status akan bergeser bergerak mendekati status akhir, sebaliknya jika statusnya False maka dia akan semakin jauh atau tetap tidak bergerak dari akhir. Nantinya kita akan mendapatkan sebuah karakter dari text saat kita berhasil dalam proses perbandingan dan akan me-reuse karakter bila kita gagal (Sistemnya hampir mirip dengan Brute-Force). Ilustrasinya Sbb :
Maksimal terjadinya False adalah n-1 dimana n adalah jumlah string dalam patern. Algoritma ini lebih baik dari Brute-Force karena lebih baik dalam segi kompleksitas dan memiliki jumlah perbandingan yang sedikit.
Referensi : Munir Rinaldi, Diktat Kuliah Strategi Algoritmik, 193, 2005.
