close

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

Algoritma Carian Teks ialah kaedah asas dalam pemprosesan teks dan mendapatkan maklumat. Algoritma ini membolehkan kami mencari dan mengenal pasti kejadian subrentetan(atau corak) dalam sekeping teks yang lebih besar.

Bagaimana ia berfungsi

  1. Mulakan dengan sekeping teks(atau dokumen) yang lebih besar dan subrentetan untuk dicari.
  2. Lelaran melalui setiap aksara teks secara berurutan.
  3. Bandingkan subrentetan dengan sebahagian daripada teks yang mempunyai panjang yang sama dengan subrentetan. Jika perlawanan ditemui, rekod kedudukan semasa.
  4. Beralih ke kedudukan seterusnya dan teruskan perbandingan.

Contoh

Pertimbangkan teks: "Mari kita cari subrentetan dalam teks ini untuk melihat cara algoritma berfungsi."

Dan subrentetan untuk mencari: "substring"

  1. Mulakan pada kedudukan 0. Bandingkan Let' dengan "substring". Tidak setanding.
  2. Beralih ke kedudukan 1. Bandingkan et's dengan "substring". Tidak setanding.
  3. Beralih ke kedudukan 2. Bandingkan t's " dengan "substring". Tiada padanan.
  4. Beralih ke kedudukan 3. Bandingkan 's s dengan "substring". Tidak setanding.
  5. Beralih ke kedudukan 4. Bandingkan se dengan "substring". Tidak setanding.
  6. Beralih ke kedudukan 5. Bandingkan sea dengan "substring". Tidak setanding.
  7. Beralih ke kedudukan 6. Bandingkan earc dengan "substring". Tidak setanding.
  8. Beralih ke kedudukan 7. Bandingkan arch dengan "substring". Tidak setanding.
  9. Beralih ke kedudukan 8. Bandingkan rch " dengan "substring". Tiada padanan.
  10. Beralih ke kedudukan 9. Bandingkan ch w dengan "substring". Tidak setanding.
  11. Beralih ke kedudukan 10. Bandingkan h wi dengan "substring". Tidak setanding.
  12. Beralih ke kedudukan 11. Bandingkan " wit dengan "substring". Tiada padanan.
  13. Beralih ke kedudukan 12. Bandingkan with dengan "substring". Tidak setanding.
  14. Beralih ke kedudukan 13. Bandingkan ithi dengan "substring". Tidak setanding.
  15. Beralih ke kedudukan 14. Bandingkan thin dengan "substring". Tidak setanding.
  16. Beralih ke kedudukan 15. Bandingkan hinn dengan "substring". Tidak setanding.
  17. Beralih ke kedudukan 16. Bandingkan in t dengan "substring". Tidak setanding.
  18. Beralih ke kedudukan 17. Bandingkan n th dengan "substring". Tidak setanding.
  19. Beralih ke kedudukan 18. Bandingkan " thi dengan "substring". Tiada padanan.
  20. Beralih ke kedudukan 19. Bandingkan this dengan "substring". Tidak setanding.
  21. Beralih ke kedudukan 20. Bandingkan his " dengan "substring". Tiada padanan.
  22. Beralih ke kedudukan 21. Bandingkan is t dengan "substring". Tidak setanding.
  23. Beralih ke kedudukan 22. Bandingkan s te  dengan "substring". Tidak setanding.
  24. Beralih ke kedudukan 23. Bandingkan ubst  dengan "substring". Tidak setanding.
  25. Beralih ke kedudukan 24. Bandingkan bstr dengan "substring". Tidak setanding.
  26. Beralih ke kedudukan 25. Bandingkan stre dengan "substring". Tidak setanding.
  27. Beralih ke kedudukan 26. Bandingkan trin  dengan "substring". Tidak setanding.
  28. Beralih ke kedudukan 27. Bandingkan ring  dengan "substring". Perlawanan ditemui, rekod kedudukan 27.

Substring "substring" ditemui pada kedudukan 27 dalam teks.

Contoh Kod dalam C++ 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

Dalam contoh ini, textSearch fungsi digunakan untuk mencari kedudukan subrentetan "substring" dalam teks. Keputusan akan menjadi vektor yang mengandungi kedudukan permulaan perlawanan.