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

Kanuni ya utafutaji wa mfuatano hutumika kupata utokeaji wa muundo maalum(mshipa mdogo) ndani ya maandishi makubwa(kamba). Algorithm hii ina jukumu muhimu katika usindikaji wa maandishi, kutafuta, na kazi za udanganyifu.

Inavyofanya kazi

1. Anza na maandishi(kamba) na muundo(mfuatano mdogo) wa kutafuta.
2. Rudia maandishi kwa herufi moja baada ya nyingine.
3. Kwa kila herufi kwenye maandishi, linganisha na herufi ya kwanza ya muundo.
4. Ikiwa kuna mechi, angalia ikiwa herufi zinazofuata pia zinalingana na muundo.
5. Ikiwa muundo unalingana kabisa, rekodi nafasi ya kuanzia ya mechi.
6. Endelea kutafuta muundo katika maandishi.

Mfano

Fikiria maandishi: "ababcababcabcabc" Na muundo: "abc"

1. Anza kwenye nafasi 0. Linganisha "a" na herufi ya kwanza "a" katika muundo.
2. Linganisha imepatikana, nenda kwa herufi zinazofuata: "b" na "b", na "a" na "c".
3. Endelea kulinganisha: "b" na "a", "a" na "b", na "b" na "c".
4. Mechi imeshindwa katika nafasi ya 2.
5. Anza tena kwenye nafasi ya 3. Linganisha "a" na herufi ya kwanza "a" katika muundo.
6. Ulinganifu uliofaulu: "a" na "a", "b" na "b", na "c" na "c".
7. Nafasi ya rekodi 3.

Mchoro "abc" unapatikana katika nafasi 0, 6, na 9.

Msimbo wa Mfano katika C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Katika mfano huu, stringSearch chaguo la kukokotoa linatumika kupata matukio ya muundo "abc" ndani ya maandishi "ababcababcabcabc". Matokeo yake yatakuwa vekta iliyo na nafasi za kuanzia za mechi.