Apa Itu Algoritma Naive String Search

Posted on by Anisa Rahma Nasution
0

Pengertian Algoritma Naive String Search

Algoritma Naive String Search adalah algoritma dasar dan langsung (brute force) untuk mencari kemunculan sebuah pola (substring) dalam sebuah teks utama (string). Algoritma ini bekerja dengan cara memeriksa setiap posisi dalam teks satu per satu, dan mencocokkan pola dari awal hingga akhir.

Algoritma ini tidak menggunakan struktur data tambahan atau preprocessing, hanya membandingkan karakter-karakter dari pola dan teks secara langsung.

Langkah-langkah Kerja Algoritma

Misalkan:

  • Teks: T dengan panjang n

  • Pola: P dengan panjang m

Langkah-langkah algoritma Naive String Search adalah:

  1. Geser pola P terhadap teks T dari kiri ke kanan, dari posisi i = 0 hingga i = n - m.

  2. Untuk setiap posisi i, bandingkan karakter P[0..m-1] dengan T[i..i+m-1].

  3. Jika semua karakter cocok → maka ditemukan kemunculan pola pada posisi i.

  4. Jika ada satu karakter yang tidak cocok → geser pola satu posisi ke kanan, lanjut ke posisi i + 1.

Kompleksitas Waktu

  • Kasus terbaik (Best case):
    Jika karakter pertama dari pola tidak cocok dengan karakter teks di banyak posisi, maka cepat: O(n)

  • Kasus terburuk (Worst case):
    Jika sebagian besar karakter cocok namun gagal di akhir (misalnya, pola dan teks sangat mirip):
    O(n * m)

Kelebihan

  • Sangat mudah dipahami dan diimplementasikan.

  • Tidak membutuhkan preprocessing.

  • Cocok untuk pencarian pola di teks pendek atau jumlah pencarian yang sedikit.

Kekurangan

  • Tidak efisien untuk teks panjang atau pola berulang.

  • Performa buruk pada kasus terburuk karena tidak memanfaatkan informasi sebelumnya (tidak ada pemotongan atau lompatan cerdas).

Contoh Ilustrasi

Teks: "ABCABCABC"
Pola: "ABC"

Langkah:

  1. Cocokkan "ABC" dengan "ABC" → cocok ✅

  2. Geser 1: "BCA" → tidak cocok ❌

  3. Geser 2: "CAB" → tidak cocok ❌

  4. Geser 3: "ABC" → cocok ✅

  5. Geser 4: "BCA" → tidak cocok ❌

  6. Geser 5: "CAB" → tidak cocok ❌

  7. Geser 6: "ABC" → cocok ✅

Maka ditemukan pola di indeks 0, 3, dan 6.

def naive_search(text, pattern):
n = len(text)
m = len(pattern)

for i in range(n – m + 1):
match = True
for j in range(m):
if text[i + j] != pattern[j]:
match = False
break
if match:
print(f”Pola ditemukan di indeks {i}”)

Berikut adalah cara kerja algoritma Naive String Search secara langkah demi langkah, agar kamu memahami logika kerjanya dengan jelas dan sistematis:

Tujuan:

Mencari apakah sebuah pola (pattern) ditemukan dalam sebuah teks (text), dan jika ya, di posisi indeks berapa.

Input:

  • text = string utama yang ingin diperiksa (panjang = n)

  • pattern = string yang ingin dicari (panjang = m)

Langkah-Langkah Kerja:

1. Perulangan Pergeseran

Lakukan pergeseran pola dari kiri ke kanan di dalam teks.
Total pergeseran yang mungkin adalah dari indeks 0 hingga n - m.

Karena jika pola dimulai di indeks n - m + 1, maka sisa teks tidak cukup untuk memuat seluruh pola.

plaintext
Loop i dari 0 sampai n - m:
Cek apakah substring text[i : i+m] == pattern

2. Pencocokan Karakter demi Karakter

Untuk setiap posisi i, cocokkan karakter dalam pattern dengan karakter di text, mulai dari:

plaintext
pattern[0] dengan text[i]
pattern[1] dengan text[i+1]
...
pattern[m-1] dengan text[i+m-1]

  • Jika semua cocok → cocok ditemukan.

  • Jika ada satu karakter tidak cocok → langsung hentikan, geser pola ke kanan.

3. Hasil Pencarian

Jika ditemukan kecocokan penuh:

  • Catat atau cetak indeks posisi i.

Contoh Nyata:

Misal:

  • text = "ABAAABCD"

  • pattern = "ABC"

i (indeks) Substring Teks Bandingkan Dengan Pola Hasil
0 ABA ABA vs ABC ❌
1 BAA BAA vs ABC ❌
2 AAA AAA vs ABC ❌
3 AAB AAB vs ABC ❌
4 ABC ✅ cocok ✅
5 BCD (tidak dicek karena panjang pattern = 3, dan indeks 5+2 = 7, masih cukup)

Algoritma Naive String Search adalah metode pencocokan pola yang sederhana namun fundamental dalam dunia pemrosesan teks. Dengan pendekatan brute force, algoritma ini memeriksa setiap kemungkinan posisi di teks utama untuk mencari kecocokan dengan pola.

Meskipun tidak efisien untuk kasus teks atau pola yang besar, algoritma ini tetap sangat berguna dalam:

  • Pembelajaran awal algoritma string.

  • Kasus-kasus sederhana yang tidak membutuhkan efisiensi tinggi.

  • Implementasi cepat dan mudah tanpa struktur tambahan.

Sebagai dasar, pemahaman algoritma ini sangat penting sebelum melangkah ke algoritma yang lebih kompleks seperti KMP, Boyer-Moore, atau Rabin-Karp, yang menawarkan efisiensi jauh lebih baik untuk kasus nyata.

Post Views: 369