Algoritmi i kërkimit të tekstit (Text Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi i Kërkimit të Tekstit është një metodë themelore në përpunimin e tekstit dhe gjetjen e informacionit. Ky algoritëm na lejon të lokalizojmë dhe identifikojmë dukuritë e një nënvargu(ose modeli) brenda një pjese më të madhe të tekstit.

Si punon

1. Filloni me një pjesë më të madhe teksti(ose dokument) dhe një nënvarg për të kërkuar.
2. Përsëriteni në çdo karakter të tekstit në mënyrë sekuenciale.
3. Krahasoni nënvargun me një pjesë të tekstit që ka të njëjtën gjatësi me nënvargun. Nëse gjendet një ndeshje, regjistro pozicionin aktual.
4. Kaloni në pozicionin tjetër dhe vazhdoni krahasimin.

Shembull

Merrni parasysh tekstin: "Le të kërkojmë një nënvarg brenda këtij teksti për të parë se si funksionon algoritmi."

Dhe nënvargu për të kërkuar: "nënstring"

1. Filloni në pozicionin 0. Krahasoni Let' me "nënstring". Asnjë ndeshje.
2. Kaloni në pozicionin 1. Krahasoni et's me "nënstring". Asnjë ndeshje.
3. Kaloni në pozicionin 2. Krahasoni t's " me "nënstring". Nuk ka përputhje.
4. Kaloni në pozicionin 3. Krahasoni 's s me "nënstring". Asnjë ndeshje.
5. Kaloni në pozicionin 4. Krahasoni se me "nënstring". Asnjë ndeshje.
6. Kaloni në pozicionin 5. Krahasoni sea me "nënstring". Asnjë ndeshje.
7. Kaloni në pozicionin 6. Krahasoni earc me "nënstring". Asnjë ndeshje.
8. Kaloni në pozicionin 7. Krahasoni arch me "nënstring". Asnjë ndeshje.
9. Kaloni në pozicionin 8. Krahasoni rch " me "nënstring". Nuk ka përputhje.
10. Kaloni në pozicionin 9. Krahasoni ch w me "nënstring". Asnjë ndeshje.
11. Kaloni në pozicionin 10. Krahasoni h wi me "nënstring". Asnjë ndeshje.
12. Kaloni në pozicionin 11. Krahasoni " wit me "nënstring". Nuk ka përputhje.
13. Kaloni në pozicionin 12. Krahasoni with me "nënstring". Asnjë ndeshje.
14. Kaloni në pozicionin 13. Krahasoni ithi me "nënstring". Asnjë ndeshje.
15. Kaloni në pozicionin 14. Krahasoni thin me "nënstring". Asnjë ndeshje.
16. Kaloni në pozicionin 15. Krahasoni hinn me "nënstring". Asnjë ndeshje.
17. Kaloni në pozicionin 16. Krahasoni in t me "nënstring". Asnjë ndeshje.
18. Kaloni në pozicionin 17. Krahasoni n th me "nënstring". Asnjë ndeshje.
19. Kaloni në pozicionin 18. Krahasoni " thi me "nënstring". Nuk ka përputhje.
20. Kaloni në pozicionin 19. Krahasoni this me "nënstring". Asnjë ndeshje.
21. Kaloni në pozicionin 20. Krahasoni his " me "nënstring". Nuk ka përputhje.
22. Kaloni në pozicionin 21. Krahasoni is t me "nënstring". Asnjë ndeshje.
23. Kaloni në pozicionin 22. Krahasoni s te  me "nënstring". Asnjë ndeshje.
24. Kaloni në pozicionin 23. Krahasoni ubst  me "nënstring". Asnjë ndeshje.
25. Kaloni në pozicionin 24. Krahasoni bstr me "nënstring". Asnjë ndeshje.
26. Kaloni në pozicionin 25. Krahasoni stre me "nënstring". Asnjë ndeshje.
27. Kaloni në pozicionin 26. Krahasoni trin  me "nënstring". Asnjë ndeshje.
28. Kaloni në pozicionin 27. Krahasoni ring  me "nënstring". Ndeshja e gjetur, pozicioni rekord 27.

Nënvargu "nënvarg" gjendet në pozicionin 27 brenda tekstit.

Shembull Kodi në 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;  
}  

Në këtë shembull, textSearch funksioni përdoret për të gjetur pozicionet e nënvargut "nënvarg" brenda tekstit. Rezultati do të jetë një vektor që përmban pozicionet fillestare të ndeshjeve.