Algoritma Carian String (String Search) dalam C++- Penjelasan, Contoh dan Kod

Algoritma carian rentetan digunakan untuk mencari kejadian corak tertentu(subrentetan) dalam teks yang lebih besar(rentetan). Algoritma ini memainkan peranan penting dalam pemprosesan teks, pencarian dan tugasan manipulasi.

Bagaimana ia berfungsi

1. Mulakan dengan teks(rentetan) dan corak(subrentetan) untuk dicari.
2. Lelaran melalui teks satu aksara pada satu masa.
3. Untuk setiap aksara dalam teks, bandingkan dengan aksara pertama corak.
4. Jika terdapat padanan, semak sama ada aksara seterusnya juga sepadan dengan corak.
5. Jika corak dipadankan sepenuhnya, rekod kedudukan permulaan perlawanan.
6. Teruskan mencari corak dalam teks.

Contoh

Pertimbangkan teks: "ababcababcabcabc" Dan corak: "abc"

1. Mulakan pada kedudukan 0. Bandingkan "a" dengan aksara pertama "a" dalam corak.
2. Padanan ditemui, beralih ke aksara seterusnya: "b" dengan "b", dan "a" dengan "c".
3. Teruskan memadankan: "b" dengan "a", "a" dengan "b", dan "b" dengan "c".
4. Perlawanan gagal di kedudukan 2.
5. Mulakan semula pada kedudukan 3. Bandingkan "a" dengan aksara pertama "a" dalam corak.
6. Padanan yang berjaya: "a" dengan "a", "b" dengan "b", dan "c" dengan "c".
7. Kedudukan rekod 3.

Corak "abc" ditemui pada kedudukan 0, 6, dan 9.

Contoh Kod dalam 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 mencari kejadian corak "abc" dalam teks "ababcababcabcabc". Keputusan akan menjadi vektor yang mengandungi kedudukan permulaan perlawanan.