String Search (String Search) Algorithm f'C++- Spjegazzjoni, Eżempju u Kodiċi

L-algoritmu ta' tfittxija ta' string jintuża biex jinstabu okkorrenzi ta' mudell speċifiku(substring) f'test akbar(string). Dan l-algoritmu għandu rwol kruċjali fl-ipproċessar tat-test, it-tiftix, u l-kompiti ta 'manipulazzjoni.

Kif taħdem

1. Ibda b'test(string) u mudell(substring) biex tfittex.
2. Ittenni fit-test karattru wieħed kull darba.
3. Għal kull karattru fit-test, qabblu mal-ewwel karattru tal-mudell.
4. Jekk ikun hemm qbil, iċċekkja jekk il-karattri sussegwenti jaqblux ukoll mal-mudell.
5. Jekk il-mudell huwa kompletament imqabbel, irreġistra l-pożizzjoni tal-bidu tal-logħba.
6. Kompli fittex il-mudell fit-test.

Eżempju

Ikkunsidra test: "ababcababcabcabc" U mudell: "abc"

1. Ibda fil-pożizzjoni 0. Qabbel "a" mal-ewwel karattru "a" fil-mudell.
2. Taqbila misjuba, imxi għall-karattri li jmiss: "b" b'"b", u "a" b'"c".
3. Kompli tqabbel: "b" ma "a", "a" ma "b", u "b" ma "ċ".
4. Il-partita falliet fil-pożizzjoni 2.
5. Ibda mill-ġdid fil-pożizzjoni 3. Qabbel "a" mal-ewwel karattru "a" fil-mudell.
6. Taqbila b'suċċess: "a" ma "a", "b" ma "b", u "ċ" ma "ċ".
7. Rekord il-pożizzjoni 3.

Il-mudell "abc" jinsab fil-pożizzjonijiet 0, 6, u 9.

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

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