ผลต่างระหว่างรุ่นของ "Kmp"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม [http://en.wik...') |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม [http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt string matching] | หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม [http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt string matching] | ||
| − | ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (<math>\pi</math>) | + | อัลกอริทึมรับ string '''P''' (pattern) และสตริง '''S''' จากนั้นหา '''P''' ใน '''S''' |
| + | |||
| + | อัลกอริทึมจะทยอย match '''P''' ใน '''S''' ไปเรื่อย ๆ เช่นถ้าเราต้องการหา <tt>ABABACA</tt> ใน <tt>ABABABACA</tt> อัลกอริทึมจะเริ่ม match ตั้งแต่ตำแหน่งแรก ดังด้านล่าง | ||
| + | |||
| + | <pre> | ||
| + | S:ABABABACA | ||
| + | P:A | ||
| + | </pre> | ||
| + | |||
| + | <pre> | ||
| + | S:ABABABACA | ||
| + | P:AB | ||
| + | </pre> | ||
| + | |||
| + | <pre> | ||
| + | S:ABABABACA | ||
| + | P:ABA | ||
| + | </pre> | ||
| + | |||
| + | <pre> | ||
| + | S:ABABABACA | ||
| + | P:ABAB | ||
| + | </pre> | ||
| + | |||
| + | <pre> | ||
| + | S:ABABABACA | ||
| + | P:ABABA | ||
| + | </pre> | ||
| + | |||
| + | จนกระทั่ง match ไม่ได้ | ||
| + | <pre> | ||
| + | S:ABABA*B*ACA | ||
| + | P:ABABA*C* | ||
| + | </pre> | ||
| + | |||
| + | ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (<math>\pi</math>, เพื่อความง่ายต่อไปจะเรียกว่า '''pi'''), ซึ่งมีนิยามดังนี้ | ||
| + | |||
| + | * '''pi(j)''' เป็นความยาวของ prefix ของ '''P[1...(j-1)]''' ที่เป็น suffix ของ '''P[1...j]''' ฟังก์ชันนี้จะใช้ในการกระโดดเมื่อเกิดการจับคู่ไม่ได้ | ||
| + | |||
| + | ด้านล่างแสดงตัวอย่างของค่า '''pi(j)''' ต่าง ๆ ของสตริง <tt>ABABACA</tt> | ||
| + | |||
| + | <pre> | ||
| + | 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 | ||
| + | </pre> | ||
รุ่นแก้ไขเมื่อ 09:22, 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*
ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (, เพื่อความง่ายต่อไปจะเรียกว่า 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
