Algoritma Pencarian String (String Search) di C++- Penjelasan, Contoh dan Kode

Algoritma pencarian string digunakan untuk menemukan kemunculan pola tertentu(substring) di dalam teks(string) yang lebih besar. Algoritma ini memainkan peran penting dalam pemrosesan teks, pencarian, dan tugas manipulasi.

Bagaimana itu bekerja

1. Mulailah dengan teks(string) dan pola(substring) untuk dicari.
2. Ulangi melalui teks satu karakter pada satu waktu.
3. Untuk setiap karakter dalam teks, bandingkan dengan karakter pertama dari pola.
4. Jika ada kecocokan, periksa apakah karakter selanjutnya juga cocok dengan polanya.
5. Jika pola benar-benar cocok, catat posisi awal pertandingan.
6. Lanjutkan mencari pola dalam teks.

Contoh

Perhatikan sebuah teks: "ababcababcabcabc" Dan sebuah pola: "abc"

1. Mulai dari posisi 0. Bandingkan "a" dengan karakter pertama "a" dalam pola.
2. Kecocokan ditemukan, pindah ke karakter berikutnya: "b" dengan "b", dan "a" dengan "c".
3. Lanjutkan mencocokkan: "b" dengan "a", "a" dengan "b", dan "b" dengan "c".
4. Pertandingan gagal di posisi 2.
5. Mulai lagi dari posisi 3. Bandingkan "a" dengan karakter pertama "a" pada pola.
6. Pertandingan yang berhasil: "a" dengan "a", "b" dengan "b", dan "c" dengan "c".
7. Rekam posisi 3.

Pola "abc" ditemukan pada posisi 0, 6, dan 9.

Contoh Kode di C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Dalam contoh ini, stringSearch fungsi digunakan untuk menemukan kemunculan pola "abc" di dalam teks "ababcababcabcabc". Hasilnya adalah vektor yang berisi posisi awal pertandingan.