Algoritmi i kërkimit të vargjeve (String Search) në C++- Shpjegimi, Shembulli dhe Kodi

Algoritmi i kërkimit të vargut përdoret për të gjetur dukuritë e një modeli specifik(nënstring) brenda një teksti(string) më të madh. Ky algoritëm luan një rol vendimtar në detyrat e përpunimit, kërkimit dhe manipulimit të tekstit.

Si punon

1. Filloni me një tekst(string) dhe një model(nënstring) për të kërkuar.
2. Përsëriteni nëpër tekst një karakter në një kohë.
3. Për çdo karakter në tekst, krahasojeni atë me karakterin e parë të modelit.
4. Nëse ka një përputhje, kontrolloni nëse karakteret e mëvonshme gjithashtu përputhen me modelin.
5. Nëse modeli përputhet plotësisht, regjistroni pozicionin e fillimit të ndeshjes.
6. Vazhdoni të kërkoni për modelin në tekst.

Shembull

Merrni parasysh një tekst: "ababcababcabcabc" dhe një model: "abc"

1. Filloni në pozicionin 0. Krahasoni "a" me karakterin e parë "a" në model.
2. Përputhja e gjetur, kaloni te karakteret vijuese: "b" me "b" dhe "a" me "c".
3. Vazhdoni të përputheni: "b" me "a", "a" me "b" dhe "b" me "c".
4. Ndeshja dështoi në pozicionin 2.
5. Filloni përsëri në pozicionin 3. Krahasoni "a" me karakterin e parë "a" në model.
6. Përputhja e suksesshme: "a" me "a", "b" me "b" dhe "c" me "c".
7. Regjistroni pozicionin 3.

Modeli "abc" gjendet në pozicionet 0, 6 dhe 9.

Shembull Kodi në 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;  
}  

Në këtë shembull, stringSearch funksioni përdoret për të gjetur dukuritë e modelit "abc" brenda tekstit "ababcababcabcabc". Rezultati do të jetë një vektor që përmban pozicionet fillestare të ndeshjeve.