Naive String Search

Cara paling sederhana mencari pattern P di dalam text T adalah dengan menggeser pattern satu per satu dan membandingkan karakter per karakter. Pendekatan ini disebut naive string search atau brute force matching. Walaupun kompleksitas worst case-nya O(n·m) — jauh lebih buruk dari algoritma linear seperti KMP — naive search tetap penting karena tiga alasan: implementasinya sangat sederhana, performanya cukup baik untuk input acak di dunia nyata, dan ia menjadi baseline untuk memahami mengapa algoritma lanjutan diperlukan. Pada Chapter ini kita akan membedah mekanismenya, menulis implementasi C++, dan menganalisis kapan pendekatan ini masih layak dipakai.

Aturan: Geser dan Bandingkan #

Naive search mengikuti dua langkah yang sangat intuitif:

Untuk setiap posisi shift i dari 0 hingga n - m, letakkan pattern P di bawah text T mulai indeks i.
Bandingkan T[i..i+m-1] dengan P[0..m-1] karakter per karakter. Bila semua cocok → catat i sebagai occurrence.

text
T = "ABABDABACDABABCABAB"
P = "ABAB"

Shift 0:  ABAB DABACDABABCABAB
          ABAB              (cocok! catat i=0)
Shift 1:   ABA B...
          ABAB              (mismatch di posisi 0: 'B' != 'A')
Shift 2:    ABAB D...
          ABAB              (mismatch lebih lanjut)
...
Shift 10:           ABAB CABAB
                    ABAB     (cocok! catat i=10)

Mekanisme: Karakter per Karakter #

Untuk setiap shift i, algoritma membandingkan T[i + j] dengan P[j] mulai j = 0. Loop berhenti saat ditemukan mismatch atau saat j == m (semua cocok).

flowchart TD Start(["i = 0"]) --> Outer{"i <= n - m?"} Outer -- Tidak --> End(["selesai"]) Outer -- Ya --> Init["j = 0"] Init --> Inner{"j < m dan T[i+j] == P[j]?"} Inner -- Ya --> Inc["j = j + 1"] Inc --> Inner Inner -- Mismatch --> NextI["i = i + 1"] Inner -- j == m --> Match["catat i sebagai occurrence"] Match --> NextI NextI --> Outer

Pada mismatch, naive search membuang seluruh informasi perbandingan sebelumnya dan maju satu langkah. Inilah yang membedakannya dari KMP atau Z-algorithm yang memanfaatkan informasi tersebut untuk melompat lebih jauh.

Kode: Implementasi C++ #

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

std::vector<int> naive_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> result;
    if (m == 0 || m > n) return result;

    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && T[i + j] == P[j]) ++j;
        if (j == m) result.push_back(i);
    }
    return result;
}

int main() {
    std::string T = "ABABDABACDABABCABAB";
    std::string P = "ABAB";

    auto occ = naive_search(T, P);
    std::cout << "T = " << T << '\n';
    std::cout << "P = " << P << '\n';
    std::cout << "Jumlah kemunculan: " << occ.size() << '\n';
    std::cout << "Indeks: ";
    for (int idx : occ) std::cout << idx << ' ';
    std::cout << '\n';

    std::string T2(5, 'A');      // "AAAAA"
    std::string P2 = "AAB";
    auto occ2 = naive_search(T2, P2);
    std::cout << "\nWorst case T=" << T2 << " P=" << P2
              << " -> " << occ2.size() << " kemunculan\n";

    return 0;
}

Output yang Dihasilkan:

text
T = ABABDABACDABABCABAB
P = ABAB
Jumlah kemunculan: 3
Indeks: 0 10 15 

Worst case T=AAAAA P=AAB -> 0 kemunculan

int n = static_cast<int>(T.size());: konversi size_t → int agar perbandingan dengan i tidak memicu signedness warning di -Wextra.
if (m == 0 || m > n) return result;: edge case. Pattern kosong tidak punya arti; pattern lebih panjang dari text pasti tidak cocok. Return vector kosong.
for (int i = 0; i <= n - m; ++i): iterasi semua posisi shift yang mungkin. Jumlah shift = n - m + 1.
while (j < m && T[i + j] == P[j]) ++j;: bandingkan karakter hingga mismatch atau habis. Short-circuit && memastikan tidak membaca T[i + m] saat j == m (yang dapat out-of-bounds untuk i = n - m).
if (j == m): bila loop berhenti karena j == m, semua karakter cocok → catat i.
occ.size() == 3 untuk contoh pertama: T = "ABABDABACDABABCABAB". Indeks 0, 10, 15 adalah posisi awal "ABAB".
Worst case demo: T = "AAAAA", P = "AAB". Setiap shift (0..3) membandingkan 2 karakter 'A' lalu mismatch di posisi ke-2 → total 8 perbandingan. Tidak ada match (memang tidak ada "AAB" di "AAAAA").

Analisis Kompleksitas #

Kasus	Perbandingan total	Kondisi pemicu
Best case	`O(n)`	Mismatch cepat di karakter pertama setiap shift
Average case	`O(n + m)`	Teks acak dengan alphabet besar
Worst case	`O(n·m)`	T = “AAAA…A”, P = “AAA…AB”

Pada best case, setiap shift hanya membandingkan 1 karakter (langsung mismatch di T[i] != P[0]) → total n - m + 1 ≈ n perbandingan.

Pada worst case, setiap shift membandingkan m karakter lalu gagal di karakter terakhir. Contoh klasik: T = "AAAAAAAA", P = "AAB". Untuk n = 8, m = 3, shift i = 0..5 (6 shift) × 3 perbandingan = 18 perbandingan ≈ n·m = 24.

Karakteristik Pathologis #

Input berikut memicu worst case:

text
T = "AAAAAAAAAAAAAAAA"  (16 buah 'A')
P = "AAAAB"

Shift 0:  AAAAAAAAAAAAAAAA
          AAAAB          (mismatch di posisi 4)
Shift 1:   AAAAAAAAAAAAAAAA
           AAAAB          (mismatch di posisi 4)
...
Shift 12:             AAAAA
                      AAAAB (mismatch di posisi 4)

Setiap shift membandingkan 5 karakter (4 ‘A’ cocok, lalu ‘B’ ≠ ‘A’). Total 12 × 5 = 60 perbandingan vs n + m = 21 bila memakai KMP.

Variasi: Pencarian dengan Wildcard #

Naive search mudah diperluas untuk dukungan wildcard sederhana:

cpp
bool match_at(const std::string& T, const std::string& P, int i) {
    for (int j = 0; j < static_cast<int>(P.size()); ++j) {
        if (P[j] != '?' && T[i + j] != P[j]) return false;
    }
    return true;
}

Karakter '?' di P dianggap cocok dengan karakter apa pun di T. Tetap O(n·m) worst case.

Kapan Naive Search Masih Layak #

Input kecil (n, m < 100): overhead preprocess KMP mungkin tidak sebanding.
Alphabet besar dan distribusi seragam (mis. teks bahasa natural): mismatch cepat di karakter pertama → average O(n + m).
Implementasi cepat untuk prototyping: satu loop sederhana, mudah di-debug.
Baseline pengujian: dipakai untuk memverifikasi hasil algoritma lanjutan.

Ringkasan #

Naive string search menggeser pattern satu per satu dan membandingkan karakter per karakter.
Best case O(n), average O(n + m), worst case O(n·m) — terutama pada input dengan prefix berulang.
Implementasi sangat sederhana: dua loop bersarang tanpa struktur bantu.
Naive membuang informasi mismatch; algoritma lanjutan (KMP, Z, Rabin-Karp) memanfaatkan info ini untuk lompatan pintar.
Masih layak untuk input kecil, alphabet besar dengan distribusi seragam, dan sebagai baseline pengujian.
Untuk pipeline produksi atau input adversarial, beralihlah ke KMP atau Aho-Corasick (Chapter berikutnya).