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

Browser text.indexOf(pattern) cukup untuk kebanyakan kasus. Tapi di balik layar, algoritma efisien bernama KMP (Knuth-Morris-Pratt) bekerja — jauh lebih cepat dari brute force.

Naive (Brute Force) — O(n × m)

Untuk setiap posisi di text, cek apakah pattern cocok:

function naiveSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) return i; // match ketemu
  }
  return -1;
}

Masalah: Di worst case (misal text="aaaaaab", pattern="aaab"), kita mengulang karakter yang sudah dicek. Kompleksitas: O(n × m).

KMP — O(n + m)

Intuisi: Ketika pattern gagal cocok di posisi tertentu, kita sudah tahu sebagian karakter yang baru saja cocok. Gunakan informasi ini untuk skip beberapa karakter, bukan mulai ulang dari nol.

Kunci KMP adalah failure function (juga disebut "lps array" = longest proper prefix that is also suffix).

Failure Function

Untuk pattern P, lps[i] = panjang prefix terpanjang dari P[0..i] yang juga merupakan suffix-nya (tidak termasuk string itu sendiri).

Contoh: pattern = "ABABCABAB"

Build Failure Function

function buildLPS(pattern) {
  const m = pattern.length;
  const lps = new Array(m).fill(0);
  let len = 0; // panjang prefix match sebelumnya

  for (let i = 1; i < m; ) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else if (len > 0) {
      len = lps[len - 1]; // fallback
    } else {
      lps[i] = 0;
      i++;
    }
  }
  return lps;
}

buildLPS("ABABCABAB"); // [0, 0, 1, 2, 0, 1, 2, 3, 4]

Search dengan Failure Function

function kmp(text, pattern) {
  const n = text.length, m = pattern.length;
  const lps = buildLPS(pattern);
  let i = 0; // index text
  let j = 0; // index pattern

  while (i < n) {
    if (text[i] === pattern[j]) {
      i++; j++;
      if (j === m) return i - m; // match!
    } else if (j > 0) {
      j = lps[j - 1]; // skip pakai info lps
    } else {
      i++;
    }
  }
  return -1;
}

kmp("ABABDABACDABABCABAB", "ABABCABAB"); // 10

Kunci speed-up: Saat mismatch, i tidak pernah mundur. Hanya j yang bisa "lompat mundur" berkat lps. Total operasi: O(n + m).

Walkthrough Singkat

text = "ABABCABAB", pattern = "ABABCABAB"

i=0..4: cocok semua (ABABC) → j=5
i=5 (A vs A): cocok → j=6
i=6 (B vs B): cocok → j=7
i=7 (A vs A): cocok → j=8
i=8 (B vs B): cocok → j=9 == m → MATCH di i=9-9=0 ✓

Tanpa KMP, jika ada mismatch di tengah, kita harus mundur. Dengan lps, mundurnya hanya sebanyak yang "aman" — sisa karakter yang sudah match tidak perlu dicek ulang.

Rabin-Karp (Rolling Hash) — Alternatif

Ide: Hitung hash dari pattern dan hash dari setiap window di text. Jika hash cocok, baru cek karakter per karakter.

Rolling hash: Saat window bergeser 1, update hash dalam O(1) alih-alih menghitung ulang O(m).

// Simplifikasi (tanpa modular hashing)
function rabinKarp(text, pattern) {
  const m = pattern.length;
  const patternHash = simpleHash(pattern);
  let windowHash = simpleHash(text.slice(0, m));

  for (let i = 0; i <= text.length - m; i++) {
    if (windowHash === patternHash && text.slice(i, i + m) === pattern) {
      return i;
    }
    if (i < text.length - m) {
      windowHash = windowHash - text.charCodeAt(i) + text.charCodeAt(i + m);
    }
  }
  return -1;
}

Average: O(n + m). Worst case (banyak hash collision): O(n × m).

Rabin-Karp sangat bagus untuk multiple pattern matching — cari banyak pattern sekaligus dengan hash.

Ringkasan Perbandingan

Di production: JavaScript indexOf, Python str.find umumnya pakai varian Boyer-Moore atau two-way string matching. KMP paling sering muncul di competitive programming dan interview karena elegant dan guaranteed O(n+m).

🎭 Analogi sehari-hari: Cari kata di buku tebal. Cara naive: ketemu huruf "B" pertama di setiap halaman, cek "Buku?" — kalau gak match di huruf ke-3, balik ke huruf "B" berikutnya, mulai dari awal. Cara KMP: kalau gak match, inget kamu udah cek "Bu" tadi — gak perlu cek ulang dari awal. Skip ke posisi yang masuk akal.

💡 Insight LPS array: Saat pattern "ABABC" gagal di posisi 4 (huruf C), kita sudah tahu "ABAB" match. "ABAB" punya prefix-suffix "AB" yang sama. Jadi text yang baru saja dicek ("ABAB") = "AB" + "AB" — kita bisa skip 2 karakter dan resume dari posisi 2 di pattern. Itulah magic LPS.

⚠️ Jebakan umum:

• Build LPS salah = seluruh KMP rusak. LPS test cases sangat penting
• Off-by-one di pattern matching — i, j, length terlibat banyak, gampang salah
• Lupa edge case pattern kosong, text kosong, pattern lebih panjang dari text
• Reimplementasi padahal indexOf cukup — kecuali butuh KMP-specific (multi-occurrence, custom match logic)

🎯 String matching algorithm pilihan:

• Casual / 1 pattern di kebanyakan text → indexOf builtin
• Banyak pattern di 1 text → Aho-Corasick (KMP multi-pattern variant)
• Worst case matters / streaming → KMP (guaranteed O(n+m))
• Random text + 1 pattern → Boyer-Moore (rata-rata O(n/m))
• Multiple pattern dengan hash → Rabin-Karp

🧪 Tebakan cepat: Cari "abab" di "ababababc" naive vs KMP. Naive: di posisi 0 match, di pos 2 cek dari awal. KMP: di pos 4 langsung skip ke 2 karena LPS. Speedup makin besar untuk pattern panjang dengan banyak repeat.

TL;DR: KMP = string matching O(n+m) dengan LPS array (failure function). Pakai info match sebelumnya untuk skip cek redundant. Foundation grep, find, dan banyak text processing. Untuk casual, indexOf cukup.