String Matching

Pencocokan pola pada string (string matching) adalah salah satu masalah klasik ilmu komputer yang muncul di banyak tempat: fitur “Find” di text editor, deteksi signature virus, pencarian kata di search engine, hingga pencocokan pola DNA. Masalah dasarnya sederhana — temukan semua kemunculan pattern P di dalam text T — tetapi efisiensi sangat penting ketika T berukuran gigabyte atau ketika harus mencari ribuan pattern sekaligus. Pada Chapter ini kita akan memetakan masalahnya, mengukur kompleksitas naive, lalu melihat kerangka berpikir yang melahirkan algoritma-algoritma lanjutan di bab-bab berikutnya.

Definisi Masalah #

Diberikan:

Text T dengan panjang n karakter.
Pattern P dengan panjang m karakter, m ≤ n.

Tujuan: temukan semua indeks i sehingga T[i..i+m-1] == P[0..m-1]. Indeks i disebut occurrence (kemunculan). Bila pattern tidak ditemukan, hasil himpunan kosong.

text
T = "ABABDABACDABABCABAB"
P = "ABAB"
       ^          ^
       i=2       i=10

Beberapa varian masalah sering muncul:

Existence: apakah P muncul di T? Cukup jawab ya/tidak.
First occurrence: indeks i pertama tempat P muncul.
All occurrences: semua indeks kemunculan.
Counting: berapa kali P muncul.
Multiple pattern: cari beberapa pattern sekaligus ({P_1, ..., P_k}).

Pendekatan Naive dan Batas Atasnya #

Cara paling intuitif: geser pattern satu per satu dari posisi 0 hingga n - m, lalu bandingkan karakter per karakter.

text
Posisi shift: 0   1   2   3   ...
              ABABDABACDABABCABAB
P disalin:    ABAB                 (shift 0: mismatch di index 2 → D vs A)
               ABAB                (shift 1: mismatch di index 0 → B vs A)
                ABAB               (shift 2: match!)

Kompleksitas: untuk setiap shift O(n) kemungkinan, kita membandingkan hingga m karakter → O(n·m) worst case. Contoh pathologis: T = "AAAA...A" (n kali), P = "AAA...B" (m kali). Setiap shift membandingkan m karakter lalu gagal di karakter terakhir.

Kasus	Kompleksitas	Contoh input
Best case	`O(n + m)`	Pattern jarang cocok sebagian
Average case (asumsi acak)	`O(n + m)`	Hampir semua mismatch cepat
Worst case	`O(n·m)`	T = “AAAA…A”, P = “AA…AB”

Kerangka Berpikir: Tiga Strategi #

Algoritma string matching dapat dikelompokkan berdasarkan strategi menghindari pekerjaan ulang:

Strategi	Inti	Contoh algoritma
Preprocess pattern	Bangun tabel/automaton dari `P` untuk melompat saat mismatch	KMP, Boyer-Moore
Rolling hash	Bandingkan hash window sliding; verifikasi saat hash cocok	Rabin-Karp
Automaton multi-pattern	Bangun trie + failure link untuk banyak pattern sekaligus	Aho-Corasick
Suffix structure	Preprocess `T` (bukan `P`) untuk query berulang	Suffix array, suffix tree, suffix automaton

Pilihan strategi bergantung pada karakteristik masalah:

Satu pattern, satu query terhadap T besar → KMP, Z-algorithm, atau Rabin-Karp.
Satu pattern, banyak query berbeda terhadap T tetap → suffix array (preprocess T sekali, query O(m log n)).
Banyak pattern sekaligus → Aho-Corasick.
Butuh substring analytics (LCP, longest repeated substring) → suffix array + LCP array.

Mekanisme Umum: Preprocess + Scan #

Sebagian besar algoritma lanjut mengikuti pola dua fase:

flowchart LR P[Pattern P] --> PP[Preprocess] PP --> ST[Struktur Bantu] T[Text T] --> SC[Scan] ST --> SC SC --> R[Hasil: semua occurrence]

Preprocess pattern: hitung tabel failure function (KMP), Z-array (Z-algorithm), atau hash (Rabin-Karp). Biaya O(m).
Scan text: geser pattern dengan lompatan pintar berdasarkan struktur bantu. Biaya O(n) atau O(n + matches).

Total: O(n + m) — linear terhadap panjang masukan, jauh lebih baik dari O(n·m) naive.

Diagram Lompatan KMP (Sneak Peek) #

flowchart TD S0["Shift 0: bandingkan penuh"] S0 --> M1{Mismatch di posisi k?} M1 -- Ya --> S1["Gunakan failure function untuk melompat"] S1 --> S2["Lanjut bandingkan tanpa ulang dari 0"] M1 -- Tidak, semua match --> SO["Catat occurrence"] S2 --> M1 SO --> S0

Bayangkan pattern "ABAB" sedang dicocokkan dengan text "ABABAB...". Saat mismatch setelah match sebagian "ABAB", kita tahu suffix "AB" dari prefix yang sudah cocok adalah juga prefix pattern — jadi tidak perlu mundur ke awal, cukup lompat ke posisi ke-2 dan lanjut. Inilah inti failure function yang akan kita bangun di Chapter KMP.

Tabel Komparasi Algoritma #

Algoritma	Preprocess	Search	Multi-pattern	Cocok untuk
Naive	—	`O(n·m)`	Tidak	Belajar, basis pembanding
KMP	`O(m)`	`O(n)`	Tidak	Single pattern, guaranteed linear
Z-algorithm	`O(m)`	`O(n)`	Tidak	Pattern matching + string analysis
Boyer-Moore	`O(m + Σ)`	`O(n/m)` best, `O(n·m)` worst	Tidak	Praktis di text editor
Rabin-Karp	`O(m)`	`O(n+m)` avg, `O(n·m)` worst	Ya (variant)	Plagiarisme, multi-pattern moderate
Aho-Corasick	`O(Σ	P_i	)`	`O(n + matches)`
Suffix array	`O(n log n)` atau `O(n)`	`O(m log n)` per pattern	Ya	Banyak query, struktur text

Σ = ukuran alphabet (256 untuk byte). |P_i| = panjang pattern ke-i.

Klasifikasi Masalah String Lanjutan #

Selain exact matching, beberapa varian sering muncul:

Approximate matching: pattern boleh berbeda ≤ k edit (lihat Chapter Edit Distance di Section 18).
Wildcards: pattern mengandung ? (satu karakter) atau * (urutan bebas).
Regular expression: pattern adalah grammar — solusi NFA/DFA (Section 23).
Longest common substring: cari substring terpanjang yang muncul di dua string — solusi suffix array + LCP.
Palindrome detection: cari substring yang dibaca sama dari dua arah (lihat Chapter String Problems).

Aplikasi Nyata #

Text editor (“Find”, “Find and Replace”): Boyer-Moore variants — sublinear average case.
Virus scanner: Aho-Corasick dengan database ribuan signature.
Search engine: inverted index (bukan string matching langsung), tetapi memakai suffix structure untuk autocomplete.
Bioinformatika: BLAST memakai hashing + local alignment untuk DNA/protein.
Plagiarisme detector: Rabin-Karp untuk fingerprint dokumen.
IDS/IPS jaringan: Aho-Corasick terhadap stream paket.

Ringkasan #

Masalah string matching: temukan semua indeks i sehingga T[i..i+m-1] == P[0..m-1].
Naive O(n·m) worst case; rata-rata O(n + m) tetapi tidak ada jaminan.
Tiga strategi utama: preprocess pattern (KMP, Z), rolling hash (Rabin-Karp), automaton multi-pattern (Aho-Corasick), atau suffix structure (suffix array/tree/automaton).
Pola umum algoritma lanjutan: preprocess O(m) + scan O(n) = total O(n + m) linear.
Pilihan algoritma bergantung pada: single vs multi pattern, T tetap vs berubah, ukuran alphabet, dan kebutuhan worst case guarantee.
Bab-bab berikutnya akan membahas tiap algoritma secara mendalam: naive (Chapter 30), KMP (Chapter 40), Z (Chapter 50), Rabin-Karp (Chapter 60), Aho-Corasick (Chapter 70), rolling hash (Chapter 80), suffix array (Chapter 90), LCP (Chapter 100), dan pola klasik (Chapter 110).