ขั้นตอนวิธีของคนูธ-มอร์ริส-แพรตต์

ในวิทยาการคอมพิวเตอร์, ขั้นตอนวิธีการค้นหาสตริง หรือ ตัวอักขระ แบบนูธ-มอร์ริส-แพรตต์ (หรืออัลกอริทึมแบบ KMP) คือ การค้นหาการเกิดขึ้นของ "คำ" (word) W ภายในส่วนที่เป็น "สตริงข้อความ" (text string) S หลัก โดยการใช้การสังเกตการณ์ว่าเมื่อเกิดความไม่แมตช์หรือไม่ตรงกันเกิดขึ้นของคำ, คำนั้น ๆ จะสามารถถูกคาดเดาได้ด้วยข้อมูลที่มีอยู่อย่างเพียงพอจริง ๆ ที่จะกำหนดว่าการจับคู่ระหว่างคำและข้อมูลที่มีอยู่นั้น จะสามารถทำให้คำหรือประโยคลำดับถัดไปนั้นจะสามารถเริ่มต้นขึ้นได้ต่อไป, จึงจะถือว่าผ่านการตรวจสอบรอบใหม่ของตัวอักขระที่จับคู่กันก่อนหน้านี้

ขั้นตอนวิธีแบบนี้ ได้ถูกคิดค้นขึ้นในปี 1974 โดย โดนัลด์ คนูธ (Donald Knuth) และวอห์น แพรตต์ (Vaughan Pratt) และนักวิชาการอิสระโดย เจมส์ เอช มอร์ริส (James H. Morris) ทั้งสามร่วมกันตีพิมพ์เผยแพร่บทความในเรื่องนี้ไว้ในปี 1977

ความเป็นมา

ขั้นตอนวิธีการจับคู่ของสตริงที่ตรงกันหรือเหมือนกันนั้นต้องการที่จะหาดัชนีเริ่มต้น m ในสตริง S[] ที่ตรงกับคำค้นหา ที่อยู่ในสตริง W[]

ขั้นตอนวิธีการที่มีความตรงไปตรงมามากที่สุด คือ การมองหาตัวอักขระที่เข้าคู่กันได้ที่มีค่าปริมาณที่มีความต่อเนื่องกันของดัชนี m, ที่มีอยู่ในตำแหน่งที่อยู่ในสตริงที่ถูกค้นหา เช่น S[m]