ผลต่างระหว่างรุ่นของ "Kmp"

รุ่นแก้ไขเมื่อ 09:34, 13 กรกฎาคม 2557

หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม 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 มาเทียบกับตัวเอง เราจะพบว่า:

ABABA
..ABA|
....A|

การที่จะขยับจุดเริ่มต้นของจุดที่จะตรวจสอบ pattern P ใน S ให้น้อยที่สุด คือ ขยับ

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

@@ แถว 35: / แถว 35: @@
 P:ABABA*C*
 </pre>
+สิ่งที่อัลกอริทึมทราบคือ ณ ตำแหน่งปัจจุบัน match มาได้ถึง ABABA แล้ว คำถามคือจะเอาข้อมูลนี้ไปใช้อย่างไรได้บ้าง?
+สังเกตว่าถ้าเอา P มาเทียบกับตัวเอง เราจะพบว่า:
+<pre style="font-family: courier">
+ABABA
+..ABA|
+....A|
+</pre>
+การที่จะขยับจุดเริ่มต้นของจุดที่จะตรวจสอบ pattern '''P''' ใน '''S''' ให้น้อยที่สุด คือ ขยับ
 ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (<math>\pi</math>, เพื่อความง่ายต่อไปจะเรียกว่า '''pi'''), ซึ่งมีนิยามดังนี้