String Matching (KMP) — Algoritma

String matching adalah masalah mencari posisi pola pattern di dalam text text. Contoh nyata: fitur Find di editor, grep, DNA matching, anti-spam. Browser…

String matching artinya mencari di mana sebuah kata pendek (pattern) muncul di dalam teks yang lebih panjang, seperti fitur Ctrl+F di browser. KMP (Knuth-Morris-Pratt, nama tiga penemunya) melakukannya tanpa pernah mundur di teks: waktu cocoknya putus di tengah jalan, dia memakai apa yang sudah dia tahu tentang pattern-nya.

🧪 Tebakan cepat: di kata ABAB, berapa huruf di bagian depan yang sama persis dengan huruf di bagian belakang (tanpa memakai seluruh katanya)? Tebak dulu, jawabannya ada di bagian "Tabel LPS".

Jangan mulai dari nol

Cari pattern ABAC di teks ABABAC. Tiga huruf pertama cocok (ABA), lalu huruf keempat gagal: teksnya B, pattern-nya C.

Cara biasa (naive) menggeser pattern satu langkah dan mencocokkan lagi dari huruf pertama pattern. Artinya dia mundur di teks dan membaca ulang huruf yang sudah pernah dicek.

KMP berpikir lain. Yang barusan cocok adalah ABA, dan ujungnya, A, sama dengan awal pattern. Jadi pattern bisa langsung ditaruh di bawah A itu dengan satu huruf sudah cocok, dan pengecekan lanjut dari huruf teks yang sama:

Langkah	Huruf teks (posisi)	Huruf pattern (posisi `j`)	Hasil
1	`ABA` (0 sampai 2)	`ABA` (0 sampai 2)	cocok semua
2	`B` (3)	`C` (3)	gagal: pattern lompat, `j` jadi 1
3	`B` (3)	`B` (1)	cocok
4	`A` (4)	`A` (2)	cocok
5	`C` (5)	`C` (3)	cocok: ketemu, mulai di posisi 2

Posisi di teks cuma maju: 0, 1, 2, 3, 3, 4, 5. Gak ada huruf teks yang dibaca dari awal lagi.

Tabel LPS

KMP tahu sejauh apa harus lompat dari tabel yang dia siapkan sebelum mencari: tabel LPS (longest proper prefix which is also suffix).

Awalan (prefix) adalah potongan dari depan. ABAB punya awalan A, AB, ABA.
Akhiran (suffix) adalah potongan dari belakang: B, AB, BAB.
Proper artinya bukan seluruh katanya sendiri.
lps[i] adalah panjang awalan terpanjang yang juga jadi akhiran, untuk potongan pattern dari huruf 0 sampai huruf i.

`i`	Potongan	Awalan yang juga akhiran	`lps[i]`
0	`A`	gak ada	0
1	`AB`	gak ada	0
2	`ABA`	`A`	1
3	`ABAB`	`AB`	2

Jadi tabel ABAB adalah [0, 0, 1, 2], dan jawaban tebakan tadi 2: AB ada di depan dan di belakang. Waktu gagal di posisi pattern j, KMP melanjutkan dari j = lps[j - 1]. Di contoh ABAC tadi, lps[2] = 1, makanya j jadi 1.

Bikin tabel LPS

function buildLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

console.log(buildLPS("ABABCABAB").join(",")); // 0,0,1,2,0,1,2,3,4
console.log(buildLPS("ABACABAB").join(",")); // 0,0,1,0,1,2,3,2

lps dimulai dengan angka 0 sebanyak panjang pattern. lps[0] selalu 0, karena satu huruf gak punya awalan proper.
len adalah panjang awalan yang sedang cocok. i adalah huruf yang sedang dicek, mulai dari 1.
Kalau pattern[i] sama dengan pattern[len], awalannya bertambah satu huruf: len++, catat di lps[i], lalu i maju.
Kalau beda dan len masih lebih dari 0, len mundur ke lps[len - 1], awalan lebih pendek yang masih mungkin cocok. i gak maju, jadi huruf yang sama dicek lagi.
Kalau beda dan len sudah 0, gak ada awalan yang cocok: lps[i] = 0, lalu i maju.

Lihat huruf terakhir ABACABAB. Sebelumnya ABA sudah cocok (len = 3), tapi huruf pattern berikutnya C, bukan B. len mundur ke lps[2] = 1 (tinggal A), lalu pattern[1] = B cocok, jadi lps[7] = 2. Mundurnya bertahap, bukan langsung ke 0.

Mencari dengan tabel

Pencariannya memakai dua penunjuk: i untuk huruf teks, j untuk huruf pattern, dua-duanya mulai dari 0.

Kalau text[i] sama dengan pattern[j], dua-duanya maju. Kalau j sampai di ujung pattern, pattern ketemu di posisi i - j.
Kalau beda dan j lebih dari 0, j = lps[j - 1]. Pattern lompat, dan huruf teks yang sama dicek lagi.
Kalau beda dan j sudah 0, gak ada yang bisa dipakai lagi, jadi i maju.

i gak pernah mundur. Di Lab, function-nya bernama kmpSearch, dan pattern ABABCABAB ketemu di posisi 10 teks ABABDABACDABABCABAB.

Misalkan teksnya n huruf dan pattern-nya m huruf. Naive bisa mengecek sampai m huruf di tiap posisi teks, jadi paling lambat O(n × m): teks dan pattern sama-sama dua kali lebih panjang, kerjanya bisa empat kali lipat. KMP O(n + m): sekali membaca teks, plus sekali bikin tabel, jadi teksnya dua kali lebih panjang, waktunya kira-kira dua kali lipat. Teks sejuta huruf dengan pattern seribu huruf: naive paling buruk sekitar satu miliar perbandingan, KMP paling banyak sekitar dua juta.

⚠️ Jebakan yang sering ketemu

len langsung jadi 0 waktu gagal. Hasilnya salah untuk pattern seperti ABACABAB. Mundur ke lps[len - 1], dan ulangi sampai cocok atau len jadi 0.
i ikut maju waktu len mundur. Huruf itu harus dicek lagi dengan awalan yang lebih pendek. Kalau i maju, satu huruf terlewat.
i mulai dari 0. Huruf 0 pasti sama dengan dirinya sendiri, jadi lps[0] salah jadi 1. Mulai dari i = 1.
Awalan sepanjang seluruh potongan. Itu gak dihitung. Untuk aaaa, lps[3] adalah 3, bukan 4.

TL;DR: KMP mencari pattern di teks tanpa pernah mundur di teks. Kuncinya tabel LPS: lps[i] = panjang awalan terpanjang (bukan seluruh potongan) yang juga jadi akhiran sampai huruf i. ABAB jadi [0, 0, 1, 2]. Waktu gagal, lanjutkan dari lps[j - 1], bukan dari nol. Saat membangun tabel, kalau gagal dan len > 0, len = lps[len - 1] tanpa memajukan i. KMP O(n + m), naive O(n × m).