Algoritem za iskanje nizov (String Search) v C++- razlaga, primer in koda

Algoritem iskanja po nizu se uporablja za iskanje pojavitev določenega vzorca(podniza) znotraj večjega besedila(niza). Ta algoritem igra ključno vlogo pri obdelavi besedila, iskanju in manipulaciji.

Kako deluje

1. Začnite z besedilom(niz) in vzorcem(podniz) za iskanje.
2. Ponavljajte besedilo en znak naenkrat.
3. Za vsak znak v besedilu ga primerjajte s prvim znakom vzorca.
4. Če obstaja ujemanje, preverite, ali se tudi naslednji znaki ujemajo z vzorcem.
5. Če se vzorec popolnoma ujema, zabeležite začetni položaj ujemanja.
6. Nadaljujte z iskanjem vzorca v besedilu.

Primer

Razmislite o besedilu: "ababcababcabcabc" In o vzorcu: "abc"

1. Začnite na položaju 0. Primerjajte "a" s prvim znakom "a" v vzorcu.
2. Ujemanje najdeno, premaknite se na naslednje znake: "b" z "b" in "a" s "c".
3. Nadaljujte z ujemanjem: "b" z "a", "a" z "b" in "b" z "c".
4. Tekma ni uspela na položaju 2.
5. Začnite znova na položaju 3. Primerjajte "a" s prvim znakom "a" v vzorcu.
6. Uspešno ujemanje: "a" z "a", "b" z "b" in "c" s "c".
7. Posnemite položaj 3.

Vzorec "abc" se nahaja na mestih 0, 6 in 9.

Primer kode v 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;  
}  

V tem primeru stringSearch se funkcija uporablja za iskanje pojavitev vzorca "abc" v besedilu "ababcababcabcabc". Rezultat bo vektor, ki vsebuje začetne položaje tekem.