อัลกอริทึม Knuth-Morris-Pratt (KMP)

บทนำ

Knuth-Morris-Pratt (KMP) เป็นอัลกอริทึมค้นหาแพทเทิร์นที่ตรวจสอบตัวอักษรจากซ้ายไปขวา เมื่อแพทเทิร์นมี Sub-pattern ซ้ำกัน จะใช้คุณสมบัตินี้เพื่อเพิ่มประสิทธิภาพ ทั้งกรณีทั่วไปและกรณีแย่ที่สุด

ความซับซ้อนของเวลา (Time Complexity)

O(n) โดย n คือความยาวข้อความหลัก

อินพุตและเอาต์พุต

Input: Main String: "AAAABAAAAABBBAAAAB", Pattern: "AAAB"
Output: Pattern found at location: 1
        Pattern found at location: 7
        Pattern found at location: 14

อัลกอริทึม

findPrefix(pattern, m, prefArray)

Input: แพทเทิร์น, ความยาวแพทเทิร์น, อาร์เรย์เก็บตำแหน่ง Prefix
Output: อาร์เรย์เก็บตำแหน่ง Prefix

Begin
    length := 0
    prefArray[0] := 0
    สำหรับดัชนี i ทุกตัวของ pattern do
        if pattern[i] = pattern[length] then
            เพิ่ม length 1
            prefArray[i] := length
        else
            if length ≠ 0 then
                length := prefArray[length - 1]
                ลด i ลง 1
            else
                prefArray[i] := 0
    done
End

kmpAlgorithm(text, pattern)

Input: ข้อความหลัก, แพทเทิร์นที่จะค้นหา
Output: ตำแหน่งที่พบแพทเทิร์น

Begin
    n := ขนาด text, m := ขนาด pattern
    เรียก findPrefix(pattern, m, prefArray)
    while i < n do
        if text[i] = pattern[j] then เพิ่ม i และ j 1
        if j = m then
            พิมพ์ตำแหน่ง (i-j)
            j := prefArray[j-1]
        else if i < n AND pattern[j] ≠ text[i] then
            if j ≠ 0 then j := prefArray[j-1]
            else เพิ่ม i 1
    done
End

ตัวอย่างโค้ด (C++)

#include<iostream>
using namespace std;

void findPrefix(string pattern, int m, int prefArray[]) {
    int length = 0;
    prefArray[0] = 0;
    for(int i = 1; i

ผลลัพธ์
Pattern found at location: 1
Pattern found at location: 7
Pattern found at location: 14