KMP Algorithm

Knuth-Morris-Pratt (KMP) เป็น algorithm สำหรับหา pattern ใน text โดยมี time complexity $O(n + m)$

แนวคิดหลัก

KMP หลีกเลี่ยงการเปรียบเทียบซ้ำโดยใช้ Failure Function (หรือ Prefix Function) ที่บอกว่าเมื่อ match ไม่สำเร็จ ควร shift pattern ไปเท่าไหร่

Failure Function (Prefix Function)

สำหรับ pattern $P$ ความยาว $m$:

• $\pi[i]$ = ความยาวของ proper prefix ที่ยาวที่สุดของ $P[0..i]$ ที่เป็น suffix ด้วย

ตัวอย่าง

Pattern: "ABABAC"

i	P[0..i]	pi[i]	Explanation
0	A	0	ไม่มี proper prefix
1	AB	0	A != B
2	ABA	1	A = A
3	ABAB	2	AB = AB
4	ABABA	3	ABA = ABA
5	ABABAC	0	ไม่มี match

Implementation

Compute Prefix Function

vector<int> computePrefix(const string& pattern) {
    int m = pattern.size();
    vector<int> pi(m, 0);
    
    int k = 0;  // length of current matching prefix
    
    for (int i = 1; i < m; i++) {
        // ถ้า mismatch, fallback ไปที่ prefix ที่สั้นกว่า
        while (k > 0 && pattern[k] != pattern[i]) {
            k = pi[k - 1];
        }
        
        // ถ้า match, ขยาย prefix
        if (pattern[k] == pattern[i]) {
            k++;
        }
        
        pi[i] = k;
    }
    
    return pi;
}

KMP Search

vector<int> kmpSearch(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    
    vector<int> pi = computePrefix(pattern);
    vector<int> matches;
    
    int j = 0;  // จำนวนตัวอักษรที่ match แล้ว
    
    for (int i = 0; i < n; i++) {
        // ถ้า mismatch, ใช้ failure function
        while (j > 0 && pattern[j] != text[i]) {
            j = pi[j - 1];
        }
        
        // ถ้า match, เพิ่ม j
        if (pattern[j] == text[i]) {
            j++;
        }
        
        // ถ้า match ทั้ง pattern
        if (j == m) {
            matches.push_back(i - m + 1);
            j = pi[j - 1];  // เตรียมหา match ถัดไป
        }
    }
    
    return matches;
}

Visualization

Text:    A B A B A B A C A B A
Pattern: A B A B A C
         
Step 1: ABABA matches, C != B
        Use pi[4] = 3, shift pattern

Text:    A B A B A B A C A B A
Pattern:     A B A B A C
             
Step 2: ABAB matches, A != B  
        Use pi[3] = 2, shift pattern

Text:    A B A B A B A C A B A
Pattern:         A B A B A C
                 
Step 3: ABABAC matches! Found at index 2

ประยุกต์ใช้งาน

1. นับจำนวน Occurrences

int countOccurrences(const string& text, const string& pattern) {
    return kmpSearch(text, pattern).size();
}

2. หา Period ของ String

Period คือ string $s$ ที่สั้นที่สุดที่ pattern = $s^k$ (ซ้ำกัน $k$ รอบ)

int findPeriod(const string& s) {
    vector<int> pi = computePrefix(s);
    int n = s.size();
    int period = n - pi[n - 1];
    
    // ตรวจสอบว่าเป็น period จริงหรือไม่
    if (n % period == 0) {
        return period;
    }
    return n;  // ไม่มี period ที่สั้นกว่าตัวมันเอง
}

3. หา Shortest Palindrome (Prepend)

string shortestPalindrome(string s) {
    string rev = s;
    reverse(rev.begin(), rev.end());
    string combined = s + "#" + rev;
    
    vector<int> pi = computePrefix(combined);
    int toAdd = s.size() - pi.back();
    
    return rev.substr(0, toAdd) + s;
}

Complexity

Operation	Time	Space
Build prefix function	$O(m)$	$O(m)$
Search	$O(n)$	$O(1)$
Total	$O(n + m)$	$O(m)$

เปรียบเทียบกับ Algorithms อื่น

Algorithm	Preprocessing	Search	Best For
Naive	$O(1)$	$O(nm)$	Short patterns
KMP	$O(m)$	$O(n)$	General purpose
Rabin-Karp	$O(m)$	$O(n)$ average	Multiple patterns
Z-function	$O(m)$	$O(n)$	Similar to KMP

Tips

1. Failure function มีประโยชน์มาก - ใช้แก้ปัญหาอื่นได้หลายอย่าง
2. ใช้ sentinel character - เมื่อต่อ string ให้ใส่ตัวคั่น เช่น #
3. ระวัง 0-indexed vs 1-indexed - ใน code ข้างต้นใช้ 0-indexed