close

Algoritam za pretraživanje teksta (Text Search) u C++- objašnjenje, primjer i kod

Algoritam pretraživanja teksta temeljna je metoda u obradi teksta i pronalaženju informacija. Ovaj nam algoritam omogućuje lociranje i prepoznavanje pojavljivanja podniza(ili uzorka) unutar većeg dijela teksta.

Kako radi

  1. Započnite s većim dijelom teksta(ili dokumenta) i podniskom za traženje.
  2. Redom iterirajte kroz svaki znak teksta.
  3. Usporedite podniz s dijelom teksta koji ima istu duljinu kao podniz. Ako se pronađe podudaranje, zabilježite trenutni položaj.
  4. Prijeđite na sljedeću poziciju i nastavite usporedbu.

Primjer

Razmotrite tekst: "Potražimo podniz unutar ovog teksta da vidimo kako algoritam radi."

I podniz za traženje: "podniz"

  1. Započnite na poziciji 0. Usporedite Let' s "podniskom". Nema podudaranja.
  2. Pomakni se na poziciju 1. Usporedi et's s "podniskom". Nema podudaranja.
  3. Pomakni se na poziciju 2. Usporedi t's " s "podniskom". Nema podudaranja.
  4. Pomakni se na poziciju 3. Usporedi 's s s "podniskom". Nema podudaranja.
  5. Pomakni se na poziciju 4. Usporedi se s "podniskom". Nema podudaranja.
  6. Pomaknite se na poziciju 5. Usporedite sea s "podniskom". Nema podudaranja.
  7. Pomaknite se na poziciju 6. Usporedite earc s "podniskom". Nema podudaranja.
  8. Pomaknite se na poziciju 7. Usporedite arch s "podniskom". Nema podudaranja.
  9. Pomakni se na poziciju 8. Usporedi rch " s "podniskom". Nema podudaranja.
  10. Pomaknite se na poziciju 9. Usporedite ch w s "podniskom". Nema podudaranja.
  11. Pomaknite se na poziciju 10. Usporedite h wi s "podniskom". Nema podudaranja.
  12. Pomakni se na poziciju 11. Usporedi " wit s "podniskom". Nema podudaranja.
  13. Pomaknite se na poziciju 12. Usporedite with s "podniskom". Nema podudaranja.
  14. Pomaknite se na poziciju 13. Usporedite ithi s "podniskom". Nema podudaranja.
  15. Pomaknite se na poziciju 14. Usporedite thin s "podniskom". Nema podudaranja.
  16. Pomaknite se na poziciju 15. Usporedite hinn s "podniskom". Nema podudaranja.
  17. Pomaknite se na poziciju 16. Usporedite in t s "podniskom". Nema podudaranja.
  18. Pomaknite se na poziciju 17. Usporedite n th s "podniskom". Nema podudaranja.
  19. Pomakni se na poziciju 18. Usporedi " thi s "podniskom". Nema podudaranja.
  20. Pomaknite se na poziciju 19. Usporedite this s "podniskom". Nema podudaranja.
  21. Pomakni se na poziciju 20. Usporedi his " s "podniskom". Nema podudaranja.
  22. Pomaknite se na poziciju 21. Usporedite is t s "podniskom". Nema podudaranja.
  23. Pomaknite se na poziciju 22. Usporedite s te  s "podniskom". Nema podudaranja.
  24. Pomaknite se na poziciju 23. Usporedite ubst  s "podniskom". Nema podudaranja.
  25. Pomaknite se na poziciju 24. Usporedite bstr s "podniskom". Nema podudaranja.
  26. Pomaknite se na poziciju 25. Usporedite stre s "podniskom". Nema podudaranja.
  27. Pomaknite se na poziciju 26. Usporedite trin  s "podniskom". Nema podudaranja.
  28. Pomaknite se na poziciju 27. Usporedite ring  s "podniskom". Podudaranje pronađeno, rekordna pozicija 27.

Podniz "substring" nalazi se na poziciji 27 unutar teksta.

Primjer koda u 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;  
}

U ovom primjeru, textSearch funkcija se koristi za pronalaženje položaja podniza "substring" unutar teksta. Rezultat će biti vektor koji sadrži početne pozicije utakmica.