close

Algoritem za iskanje besedila (Text Search) v C++- razlaga, primer in koda

Algoritem iskanja po besedilu je temeljna metoda pri obdelavi besedila in iskanju informacij. Ta algoritem nam omogoča, da poiščemo in identificiramo pojavitve podniza(ali vzorca) znotraj večjega dela besedila.

Kako deluje

  1. Začnite z večjim delom besedila(ali dokumenta) in podnizom za iskanje.
  2. Zaporedoma preletite vsak znak besedila.
  3. Primerjajte podniz z delom besedila, ki ima enako dolžino kot podniz. Če se najde ujemanje, zabeležite trenutni položaj.
  4. Premaknite se na naslednji položaj in nadaljujte s primerjavo.

Primer

Razmislite o besedilu: "Poiščimo podniz v tem besedilu, da vidimo, kako deluje algoritem."

In podniz za iskanje: "substring"

  1. Začnite na položaju 0. Primerjajte Let' s "podnizom". Ni ujemanj.
  2. Premakni se na položaj 1. Primerjaj et's s "podnizom". Ni ujemanj.
  3. Premakni se na položaj 2. Primerjaj t's " s "podnizom". Ni ujemanja.
  4. Premakni se na položaj 3. Primerjaj 's s s "podnizom". Ni ujemanj.
  5. Premakni se na položaj 4. Primerjaj se s "podnizom". Ni ujemanj.
  6. Premakni se na položaj 5. Primerjaj sea s "podnizom". Ni ujemanj.
  7. Premakni se na položaj 6. Primerjaj earc s "podnizom". Ni ujemanj.
  8. Premakni se na položaj 7. Primerjaj arch s "podnizom". Ni ujemanj.
  9. Premakni se na položaj 8. Primerjaj rch " s "podnizom". Ni ujemanja.
  10. Premakni se na položaj 9. Primerjaj ch w s "podnizom". Ni ujemanj.
  11. Premakni se na položaj 10. Primerjaj h wi s "podnizom". Ni ujemanj.
  12. Premakni se na položaj 11. Primerjaj " wit s "podnizom". Ni ujemanja.
  13. Premakni se na položaj 12. Primerjaj with s "podnizom". Ni ujemanj.
  14. Premakni se na položaj 13. Primerjaj ithi s "podnizom". Ni ujemanj.
  15. Premakni se na položaj 14. Primerjaj thin s "podnizom". Ni ujemanj.
  16. Premakni se na položaj 15. Primerjaj hinn s "podnizom". Ni ujemanj.
  17. Premakni se na položaj 16. Primerjaj in t s "podnizom". Ni ujemanj.
  18. Premakni se na položaj 17. Primerjaj n th s "podnizom". Ni ujemanj.
  19. Premakni se na položaj 18. Primerjaj " thi s "podnizom". Ni ujemanja.
  20. Premakni se na položaj 19. Primerjaj this s "podnizom". Ni ujemanj.
  21. Premakni se na položaj 20. Primerjaj his " s "podnizom". Ni ujemanja.
  22. Premakni se na položaj 21. Primerjaj is t s "podnizom". Ni ujemanj.
  23. Premakni se na položaj 22. Primerjaj s te  s "podnizom". Ni ujemanj.
  24. Premakni se na položaj 23. Primerjaj ubst  s "podnizom". Ni ujemanj.
  25. Premakni se na položaj 24. Primerjaj bstr s "podnizom". Ni ujemanj.
  26. Premakni se na položaj 25. Primerjaj stre s "podnizom". Ni ujemanj.
  27. Premakni se na položaj 26. Primerjaj trin  s "podnizom". Ni ujemanj.
  28. Premakni se na položaj 27. Primerjaj ring  s "podnizom". Ujemanje najdeno, rekordno mesto 27.

Podniz "substring" se nahaja na mestu 27 znotraj besedila.

Primer kode v 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;  
}

V tem primeru textSearch se funkcija uporablja za iskanje položajev podniza "substring" v besedilu. Rezultat bo vektor, ki vsebuje začetne položaje tekem.