close

Algoritmu tat- Tiftix tat-Test (Text Search) f'C++- Spjegazzjoni, Eżempju u Kodiċi

L-algoritmu tat-Tiftix tat-Test huwa metodu fundamentali fl-ipproċessar tat-test u l-irkupru tal-informazzjoni. Dan l-algoritmu jippermettilna nsibu u nidentifikaw okkorrenzi ta' substring(jew mudell) f'biċċa ikbar ta' test.

Kif taħdem

  1. Ibda b'biċċa test akbar(jew dokument) u substring biex tfittex.
  2. Itteri f'kull karattru tat-test b'mod sekwenzjali.
  3. Qabbel is-substring ma' porzjon tat-test li għandu l-istess tul bħas-substring. Jekk tinstab taqbila, irreġistra l-pożizzjoni attwali.
  4. Imxi għall-pożizzjoni li jmiss u kompli l-paragun.

Eżempju

Ikkunsidra t-test: "Ejja nfittxu substring f'dan it-test biex tara kif jaħdem l-algoritmu."

U s-substring li trid tfittex: "substring"

  1. Ibda fil-pożizzjoni 0. Qabbel Let' ma '"substring". Ebda taqbila.
  2. Imxi għall-pożizzjoni 1. Qabbel et's ma '"substring". Ebda taqbila.
  3. Imxi għall-pożizzjoni 2. Qabbel t's " ma' "substring". L-ebda taqbila.
  4. Imxi għall-pożizzjoni 3. Qabbel 's s ma '"substring". Ebda taqbila.
  5. Imxi għall-pożizzjoni 4. Qabbel se ma '"substring". Ebda taqbila.
  6. Imxi għall-pożizzjoni 5. Qabbel sea ma '"substring". Ebda taqbila.
  7. Imxi għall-pożizzjoni 6. Qabbel earc ma '"substring". Ebda taqbila.
  8. Imxi għall-pożizzjoni 7. Qabbel arch ma '"substring". Ebda taqbila.
  9. Imxi għall-pożizzjoni 8. Qabbel rch " ma '"substring". L-ebda taqbila.
  10. Imxi għall-pożizzjoni 9. Qabbel ch w ma '"substring". Ebda taqbila.
  11. Imxi għall-pożizzjoni 10. Qabbel h wi ma '"substring". Ebda taqbila.
  12. Imxi għall-pożizzjoni 11. Qabbel " wit ma' "substring". L-ebda taqbila.
  13. Imxi għall-pożizzjoni 12. Qabbel with ma '"substring". Ebda taqbila.
  14. Imxi għall-pożizzjoni 13. Qabbel ithi ma '"substring". Ebda taqbila.
  15. Imxi għall-pożizzjoni 14. Qabbel thin ma '"substring". Ebda taqbila.
  16. Imxi għall-pożizzjoni 15. Qabbel hinn ma '"substring". Ebda taqbila.
  17. Imxi għall-pożizzjoni 16. Qabbel in t ma '"substring". Ebda taqbila.
  18. Imxi għall-pożizzjoni 17. Qabbel n th ma '"substring". Ebda taqbila.
  19. Imxi għall-pożizzjoni 18. Qabbel " thi ma '"substring". L-ebda taqbila.
  20. Imxi għall-pożizzjoni 19. Qabbel this ma '"substring". Ebda taqbila.
  21. Imxi għall-pożizzjoni 20. Qabbel his " ma '"substring". L-ebda taqbila.
  22. Imxi għall-pożizzjoni 21. Qabbel is t ma '"substring". Ebda taqbila.
  23. Imxi għall-pożizzjoni 22. Qabbel s te  ma '"substring". Ebda taqbila.
  24. Imxi għall-pożizzjoni 23. Qabbel ubst  ma '"substring". Ebda taqbila.
  25. Imxi għall-pożizzjoni 24. Qabbel bstr ma '"substring". Ebda taqbila.
  26. Imxi għall-pożizzjoni 25. Qabbel stre ma '"substring". Ebda taqbila.
  27. Imxi għall-pożizzjoni 26. Qabbel trin  ma '"substring". Ebda taqbila.
  28. Imxi għall-pożizzjoni 27. Qabbel ring  ma '"substring". Taqbila misjuba, pożizzjoni rekord 27.

Is-substring "substring" tinsab fil-pożizzjoni 27 fit-test.

Eżempju Kodiċi f'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;  
}

F'dan l-eżempju, il- textSearch funzjoni tintuża biex issib il-pożizzjonijiet tas-substring "substring" fit-test. Ir-riżultat se jkun vettur li jkun fih il-pożizzjonijiet tal-bidu tal-logħbiet.