close

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

Algoritma Text Search adalah metode mendasar dalam pemrosesan teks dan pencarian informasi. Algoritma ini memungkinkan kita untuk menemukan dan mengidentifikasi kemunculan substring(atau pola) dalam potongan teks yang lebih besar.

Bagaimana itu bekerja

  1. Mulailah dengan potongan teks(atau dokumen) yang lebih besar dan substring untuk dicari.
  2. Ulangi setiap karakter teks secara berurutan.
  3. Bandingkan substring dengan bagian teks yang memiliki panjang yang sama dengan substring. Jika kecocokan ditemukan, catat posisi saat ini.
  4. Pindah ke posisi berikutnya dan lanjutkan perbandingan.

Contoh

Pertimbangkan teksnya: "Mari kita cari substring di dalam teks ini untuk melihat cara kerja algoritme."

Dan substring untuk mencari: "substring"

  1. Mulai dari posisi 0. Bandingkan Let' dengan "substring". Tidak cocok.
  2. Pindah ke posisi 1. Bandingkan et's dengan "substring". Tidak cocok.
  3. Pindah ke posisi 2. Bandingkan t's " dengan "substring". Tidak cocok.
  4. Pindah ke posisi 3. Bandingkan 's s dengan "substring". Tidak cocok.
  5. Pindah ke posisi 4. Bandingkan se dengan "substring". Tidak cocok.
  6. Pindah ke posisi 5. Bandingkan sea dengan "substring". Tidak cocok.
  7. Pindah ke posisi 6. Bandingkan earc dengan "substring". Tidak cocok.
  8. Pindah ke posisi 7. Bandingkan arch dengan "substring". Tidak cocok.
  9. Pindah ke posisi 8. Bandingkan rch " dengan "substring". Tidak cocok.
  10. Pindah ke posisi 9. Bandingkan ch w dengan "substring". Tidak cocok.
  11. Pindah ke posisi 10. Bandingkan h wi dengan "substring". Tidak cocok.
  12. Pindah ke posisi 11. Bandingkan " wit dengan "substring". Tidak cocok.
  13. Pindah ke posisi 12. Bandingkan with dengan "substring". Tidak cocok.
  14. Pindah ke posisi 13. Bandingkan ithi dengan "substring". Tidak cocok.
  15. Pindah ke posisi 14. Bandingkan thin dengan "substring". Tidak cocok.
  16. Pindah ke posisi 15. Bandingkan hinn dengan "substring". Tidak cocok.
  17. Pindah ke posisi 16. Bandingkan in t dengan "substring". Tidak cocok.
  18. Pindah ke posisi 17. Bandingkan n th dengan "substring". Tidak cocok.
  19. Pindah ke posisi 18. Bandingkan " thi dengan "substring". Tidak cocok.
  20. Pindah ke posisi 19. Bandingkan this dengan "substring". Tidak cocok.
  21. Pindah ke posisi 20. Bandingkan his " dengan "substring". Tidak cocok.
  22. Pindah ke posisi 21. Bandingkan is t dengan "substring". Tidak cocok.
  23. Pindah ke posisi 22. Bandingkan s te  dengan "substring". Tidak cocok.
  24. Pindah ke posisi 23. Bandingkan ubst  dengan "substring". Tidak cocok.
  25. Pindah ke posisi 24. Bandingkan bstr dengan "substring". Tidak cocok.
  26. Pindah ke posisi 25. Bandingkan stre dengan "substring". Tidak cocok.
  27. Pindah ke posisi 26. Bandingkan trin  dengan "substring". Tidak cocok.
  28. Pindah ke posisi 27. Bandingkan ring  dengan "substring". Kecocokan ditemukan, catat posisi 27.

Substring "substring" ditemukan di posisi 27 dalam teks.

Contoh Kode di 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 posisi substring "substring" di dalam teks. Hasilnya adalah vektor yang berisi posisi awal pertandingan.