Jelaskan Pseudocode dari Algoritma Knuth-Morris-Pratt

Berikut adalah pseudocode algoritme KMP pada fase pra-pencarian:

input P: array[0..n-1] of char,

input/output kmpNext: array[0..n] of integer

while (i < n) {

while (j > -1 and not(P[i] = P[j]))

Dan berikut adalah pseudocode algoritme KMP pada fase pencarian:

input P: array[0..n-1] of char,

input T: array[0..m-1] of char,

output ketemu: array[0..m-1] of boolean

while (j < n and T[i+j] = P[j]) do

Algoritme ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritme ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alpabet