Knuth-Morris-Pratt

Algoritma Knuth-Morris-Pratt (KMP) memecahkan masalah string matching dengan jaminan linear O(n + m) di semua kasus, tanpa terkecuali worst case. Kunci KMP adalah failure function: sebuah tabel sepanjang m yang menyimpan, untuk setiap prefix pattern P[0..i], panjang longest proper prefix yang juga merupakan suffix dari prefix tersebut. Tabel ini memberi tahu algoritma seberapa jauh bisa melompat maju saat terjadi mismatch, tanpa pernah memundurkan indeks text. Pada Chapter ini kita akan membangun failure function dari nol, memvisualisasikannya, lalu menggunakannya untuk search.

Aturan: Manfaatkan Prefix yang Sudah Cocok #

Saat naive search menemui mismatch setelah q karakter pattern cocok, ia membuang semua info dan maju satu langkah. KMP bertanya: dari q karakter yang sudah cocok, berapa banyak karakter di akhir yang juga merupakan prefix dari pattern? Karakter tersebut tidak perlu dibandingkan ulang karena sudah pasti cocok.

Contoh: pattern "ABABC". Setelah cocok 4 karakter "ABAB", suffix "AB" adalah juga prefix "AB" dari pattern. Bila karakter ke-5 ('C') mismatch, kita tahu 2 karakter berikutnya sudah pasti "AB" — tidak perlu mundur ke awal, langsung lompat ke posisi q = 2.

Mekanisme: Failure Function #

Definisi: f[i] = panjang longest proper prefix dari P[0..i] yang juga merupakan suffix dari P[0..i]. Proper berarti bukan seluruh string itu sendiri.

Untuk pattern "ABABC":

text
i   : 0 1 2 3 4
P   : A B A B C
f[i]: 0 0 1 2 0

f[0] = 0: prefix "A", proper prefix kosong.
f[1] = 0: prefix "AB" — prefix {"A"}, suffix {"B"}. Tidak ada yang sama.
f[2] = 1: prefix "ABA" — prefix {"A","AB"}, suffix {"A","BA"}. "A" cocok → panjang 1.
f[3] = 2: prefix "ABAB" — prefix {"A","AB","ABA"}, suffix {"B","AB","BAB"}. "AB" cocok → panjang 2.
f[4] = 0: prefix "ABABC" — tidak ada proper prefix = suffix.

flowchart TD A["i = 0: f[0] = 0"] --> B["i = 1, k = f[0] = 0"] B --> C{"P[1] == P[0]?"} C -- Tidak --> D["f[1] = 0"] D --> E["i = 2, k = f[1] = 0"] E --> F{"P[2] == P[0]?"} F -- Ya --> G["k = 1, f[2] = 1"] G --> H["i = 3, k = f[2] = 1"] H --> I{"P[3] == P[1]?"} I -- Ya --> J["k = 2, f[3] = 2"] J --> K["i = 4, k = f[3] = 2"] K --> L{"P[4] == P[2]?"} L -- Tidak --> M["k = f[1] = 0"] M --> N{"P[4] == P[0]?"} N -- Tidak --> O["f[4] = 0"]

Kode: Build Failure Function #

cpp
#include <iostream>
#include <string>
#include <vector>

std::vector<int> build_failure(const std::string& P) {
    int m = static_cast<int>(P.size());
    std::vector<int> f(m, 0);
    for (int i = 1; i < m; ++i) {
        int k = f[i - 1];
        while (k > 0 && P[i] != P[k]) k = f[k - 1];
        if (P[i] == P[k]) ++k;
        f[i] = k;
    }
    return f;
}

int main() {
    std::string P = "ABABC";
    std::vector<int> f = build_failure(P);
    std::cout << "Pattern: " << P << '\n';
    std::cout << "Index  : ";
    for (int i = 0; i < static_cast<int>(P.size()); ++i) std::cout << i << ' ';
    std::cout << "\nf[i]   : ";
    for (int v : f) std::cout << v << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Pattern: ABABC
Index  : 0 1 2 3 4 
f[i]   : 0 0 1 2 0 

std::vector<int> f(m, 0);: inisialisasi dengan 0. f[0] = 0 selalu (proper prefix kosong).
int k = f[i - 1];: ambil panjang prefix-suffix terpanjang dari prefix sebelumnya. Kita coba perpanjang dengan P[i].
while (k > 0 && P[i] != P[k]) k = f[k - 1];: bila tidak bisa diperpanjang, mundur ke failure function k - 1 sebelumnya. Ini recursive fallback — kita tidak pernah mundur lebih dari O(m) total.
if (P[i] == P[k]) ++k;: bila cocok, perpanjang sebesar 1.
f[i] = k;: simpan hasil.
Amortized analysis: variabel k naik maksimal 1 per iterasi i, dan turun paling tidak sekali per iterasi. Total perubahan k dibatasi O(m), sehingga seluruh build O(m).

Kode: KMP Search #

cpp
#include <iostream>
#include <string>
#include <vector>

std::vector<int> build_failure(const std::string& P) {
    int m = static_cast<int>(P.size());
    std::vector<int> f(m, 0);
    for (int i = 1; i < m; ++i) {
        int k = f[i - 1];
        while (k > 0 && P[i] != P[k]) k = f[k - 1];
        if (P[i] == P[k]) ++k;
        f[i] = k;
    }
    return f;
}

std::vector<int> kmp_search(const std::string& T, const std::string& P) {
    int n = static_cast<int>(T.size());
    int m = static_cast<int>(P.size());
    std::vector<int> f = build_failure(P);
    std::vector<int> result;
    int q = 0;  // jumlah karakter P yang sudah cocok
    for (int i = 0; i < n; ++i) {
        while (q > 0 && T[i] != P[q]) q = f[q - 1];
        if (T[i] == P[q]) ++q;
        if (q == m) {
            result.push_back(i - m + 1);
            q = f[q - 1];
        }
    }
    return result;
}

int main() {
    std::string P = "ABABC";
    std::string T = "ABABDABACDABABCABABABABCX";

    std::vector<int> f = build_failure(P);
    std::cout << "Pattern: " << P << '\n';
    std::cout << "Index  : ";
    for (int i = 0; i < static_cast<int>(P.size()); ++i) std::cout << i << ' ';
    std::cout << "\nf[i]   : ";
    for (int v : f) std::cout << v << ' ';
    std::cout << "\n\n";

    auto occ = kmp_search(T, P);
    std::cout << "T = " << T << '\n';
    std::cout << "P = " << P << '\n';
    std::cout << "Indeks kemunculan: ";
    for (int idx : occ) std::cout << idx << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Pattern: ABABC
Index  : 0 1 2 3 4 
f[i]   : 0 0 1 2 0 


T = ABABDABACDABABCABABABABCX
P = ABABC
Indeks kemunculan: 10 19 

int q = 0;: jumlah karakter P yang sudah cocok berurutan. Indeks text i hanya maju, q bisa naik-turun.
while (q > 0 && T[i] != P[q]) q = f[q - 1];: bila mismatch dan q > 0, lompat ke f[q - 1]. Tidak mundur i — kunci linearitas.
if (T[i] == P[q]) ++q;: bila cocok (atau setelah lompat q = 0), perpanjang q.
if (q == m): full match → catat indeks awal i - m + 1.
q = f[q - 1]; setelah match: lanjut mencari occurrence berikutnya. Tanpa ini, kita hanya menemukan non-overlapping matches. Dengan failure function, kita bisa menemukan overlapping (mis. P = "AA", T = "AAAA" → semua 3 indeks).
Indeks 10 dan 19: dua kemunculan "ABABC" di text "ABABDABACDABABCABABABABCX".

Trace Step-by-Step #

Mari amati detik-detik kritis saat KMP menemui mismatch setelah match panjang:

text
T = "...ABABABABC..."
            ^^^^^
            i = 14 (C), q sebelumnya = 4

Step: T[14]='C' != P[4]='C'? Sama! q = 5 = m → match pada shift i-m+1 = 10.

Setelah match: q = f[4] = 0. Lanjut dari i = 15.

Pada titik mismatch tanpa match (mis. T = "ABABX...", mismatch di posisi q = 4):

text
T = "...ABABX..."
P = "ABABC"
q = 4 (karakter 'A','B','A','B' sudah cocok)
T[4] = 'X' != P[4] = 'C'

KMP: q = f[q-1] = f[3] = 2 (loncat ke posisi q=2 di P)
Sekarang cek T[4] = 'X' vs P[2] = 'A'? Tidak cocok.
q = f[1] = 0.
Cek T[4] = 'X' vs P[0] = 'A'? Tidak cocok. q tetap 0.
Lanjut ke i = 5.

Tanpa KMP, naive search akan memundurkan indeks ke i = 1 lalu i = 2 dan seterusnya, membandingkan ulang dari awal.

Kompleksitas #

Tahap	Waktu	Ruang
Build failure function	`O(m)`	`O(m)`
Search	`O(n)`	`O(m)` untuk tabel
Total	`O(n + m)`	`O(m)`

Bukti linearitas: setiap iterasi loop luar (i++) menambah i + q minimal 1 (karena i naik 1, q naik maksimal 1). Setiap iterasi loop dalam (q = f[q-1]) mengurangi q minimal 1. Variabel i + q monoton naik dari 0 hingga n + m → total operasi O(n + m).

Aplikasi KMP #

String matching sekali jalan: search dalam text editor, log scanner.
Pattern matching berulang: panggil build_failure sekali, lalu search berkali-kali.
Deteksi period: bila n % (n - f[n-1]) == 0, maka pattern periodik dengan periode n - f[n-1].
Sub-string di list string: filter, klasifikasi teks.

Variasi dan Catatan #

KMP dengan wildcard: tidak langsung didukung karena failure function butuh exact match.
Boyer-Moore vs KMP: BM sering lebih cepat di praktik (sublinear average) karena lompatan dari belakang, tetapi tidak ada jaminan worst case linear. KMP unggul di worst case guarantee.
Streaming: KMP cocok untuk text stream karena hanya maju, tidak perlu buffer penuh.

Ringkasan #

KMP menyelesaikan string matching dengan jaminan linear O(n + m) di semua kasus.
Failure function f[i] = panjang longest proper prefix yang juga suffix dari P[0..i].
Build failure function O(m) dengan loop + recursive fallback.
Search O(n): indeks text hanya maju, q naik-turun via failure function, tidak pernah mundur.
Cocok untuk: single pattern, guaranteed linear, streaming text, deteksi period.
Tidak cocok untuk: multiple pattern (gunakan Aho-Corasick), banyak query terhadap text tetap (gunakan suffix array).