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*

สิ่งที่อัลกอริทึมทราบคือ ณ ตำแหน่งปัจจุบัน match มาได้ถึง ABABA แล้ว คำถามคือจะเอาข้อมูลนี้ไปใช้อย่างไรได้บ้าง?

สังเกตว่าถ้าเอา P มาเทียบกับตัวเอง โดยพิจารณาเฉพาะ prefix ABABA ที่ถูก match ไปแล้ว เราจะพบว่า:

P:ABABA|
  ..ABA|
  ....A|

ดังนั้นการที่จะขยับจุดเริ่มต้นของจุดที่จะตรวจสอบ pattern P ใน S ให้น้อยที่สุด คือ ขยับไปสองตำแหน่ง นั่งคือ ดูจากความยาวของ ABABA ลบด้วยความยาวของ ABA แล้วสองสตริงนี้คืออะไร?

สังเกตว่า ถ้าเรา match มาได้ถึง ABABA แล้ว เราจะกระโดดไปน้อยสุด เราต้องหา suffix ที่ยาวที่สุดของ ABABA ที่เป็น prefix ของ ABABA ด้วยนั่งเอง

ส่วนที่ยุ่งยากที่สุดคือการคำนวน 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