close

Algorithm ya Utafutaji wa Maandishi (Text Search) katika C++- Maelezo, Mfano na Msimbo

Algorithm ya Utafutaji wa Maandishi ni njia ya msingi katika usindikaji wa maandishi na urejeshaji wa habari. Kanuni hii huturuhusu kupata na kutambua matukio ya kamba ndogo(au muundo) ndani ya kipande kikubwa cha maandishi.

Inavyofanya kazi

  1. Anza na kipande kikubwa cha maandishi(au hati) na kifungu kidogo cha kutafuta.
  2. Rudia kupitia kila herufi ya maandishi kwa kufuatana.
  3. Linganisha kamba ndogo na sehemu ya maandishi ambayo ina urefu sawa na kamba ndogo. Ikiwa mechi imepatikana, rekodi nafasi ya sasa.
  4. Nenda kwenye nafasi inayofuata na uendelee kulinganisha.

Mfano

Fikiria maandishi: "Hebu tutafute kamba ndogo ndani ya maandishi haya ili kuona jinsi algoriti inavyofanya kazi."

Na kifungu kidogo cha kutafuta: "substring"

  1. Anza kwenye nafasi 0. Linganisha Let' na "substring". Hakuna mechi.
  2. Sogeza hadi nafasi ya 1. Linganisha et's na "substring". Hakuna mechi.
  3. Sogeza hadi nafasi ya 2. Linganisha t's " na "substring". Hakuna mechi.
  4. Sogeza hadi nafasi ya 3. Linganisha 's s na "substring". Hakuna mechi.
  5. Sogeza hadi nafasi ya 4. Linganisha se na "substring". Hakuna mechi.
  6. Sogeza hadi nafasi ya 5. Linganisha sea na "substring". Hakuna mechi.
  7. Sogeza hadi nafasi ya 6. Linganisha earc na "substring". Hakuna mechi.
  8. Sogeza hadi nafasi ya 7. Linganisha arch na "substring". Hakuna mechi.
  9. Sogeza hadi nafasi ya 8. Linganisha rch " na "substring". Hakuna mechi.
  10. Sogeza hadi nafasi ya 9. Linganisha ch w na "substring". Hakuna mechi.
  11. Sogeza hadi nafasi ya 10. Linganisha h wi na "substring". Hakuna mechi.
  12. Sogeza hadi nafasi ya 11. Linganisha " wit na "substring". Hakuna mechi.
  13. Sogeza hadi nafasi ya 12. Linganisha with na "substring". Hakuna mechi.
  14. Sogeza hadi nafasi ya 13. Linganisha ithi na "substring". Hakuna mechi.
  15. Sogeza hadi nafasi ya 14. Linganisha thin na "msururu mdogo". Hakuna mechi.
  16. Sogeza hadi nafasi ya 15. Linganisha hinn na "substring". Hakuna mechi.
  17. Sogeza hadi nafasi ya 16. Linganisha in t na "substring". Hakuna mechi.
  18. Sogeza hadi nafasi ya 17. Linganisha n th na "substring". Hakuna mechi.
  19. Sogeza hadi nafasi ya 18. Linganisha " thi na "substring". Hakuna mechi.
  20. Sogeza hadi nafasi ya 19. Linganisha this na "substring". Hakuna mechi.
  21. Sogeza hadi nafasi ya 20. Linganisha his " na "substring". Hakuna mechi.
  22. Sogeza hadi nafasi ya 21. Linganisha is t na "substring". Hakuna mechi.
  23. Sogeza hadi nafasi ya 22. Linganisha s te  na "substring". Hakuna mechi.
  24. Sogeza hadi nafasi ya 23. Linganisha ubst  na "substring". Hakuna mechi.
  25. Sogeza hadi nafasi ya 24. Linganisha bstr na "substring". Hakuna mechi.
  26. Sogeza hadi nafasi ya 25. Linganisha stre na "substring". Hakuna mechi.
  27. Sogeza hadi nafasi ya 26. Linganisha trin  na "substring". Hakuna mechi.
  28. Sogeza hadi nafasi ya 27. Linganisha ring  na "substring". Mechi imepatikana, rekodi nafasi ya 27.

Mstari mdogo "msururu" unapatikana katika nafasi ya 27 ndani ya maandishi.

Msimbo wa Mfano katika 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;  
}

Katika mfano huu, textSearch chaguo za kukokotoa hutumika kupata nafasi za "mfuatano mdogo" ndani ya maandishi. Matokeo yake yatakuwa vekta iliyo na nafasi za kuanzia za mechi.