Kmp

หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม Knuth–Morris–Pratt string matching

อัลกอริทึมรับ string P (pattern) และสตริง S จากนั้นหา P ใน S

อัลกอริทึมจะทยอย match P ใน S ไปเรื่อย ๆ เช่นถ้าเราต้องการหา ABABACA ใน ABABABACA อัลกอริทึมจะเริ่ม match ตั้งแต่ตำแหน่งแรก ดังด้านล่าง

S:ABABABACA
P:A

S:ABABABACA
P:AB

S:ABABABACA
P:ABA

S:ABABABACA
P:ABAB

S:ABABABACA
P:ABABA

จนกระทั่ง match ไม่ได้

S:ABABA*B*ACA
P:ABABA*C*

ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function ($\pi$, เพื่อความง่ายต่อไปจะเรียกว่า pi), ซึ่งมีนิยามดังนี้

• pi(j) เป็นความยาวของ prefix ของ P[1...(j-1)] ที่เป็น suffix ของ P[1...j] ฟังก์ชันนี้จะใช้ในการกระโดดเมื่อเกิดการจับคู่ไม่ได้

ด้านล่างแสดงตัวอย่างของค่า pi(j) ต่าง ๆ ของสตริง ABABACA

A B A B A C A
A B
A B A
A B A B 
A B A B A 
A B A B A C
A B A B A C A