Algoritam pretraživanja niza (String Search) u C++- objašnjenje, primjer i kod

Algoritam pretraživanja niza koristi se za pronalaženje pojavljivanja određenog uzorka(podniza) unutar većeg teksta(niza). Ovaj algoritam ima ključnu ulogu u zadacima obrade teksta, pretraživanja i manipulacije.

Kako radi

1. Započnite s tekstom(string) i uzorkom(podstring) za traženje.
2. Iterirajte kroz tekst jedan po jedan znak.
3. Za svaki znak u tekstu usporedite ga s prvim znakom uzorka.
4. Ako postoji podudaranje, provjerite odgovaraju li i sljedeći znakovi uzorku.
5. Ako je uzorak potpuno usklađen, zabilježite početnu poziciju podudaranja.
6. Nastavite tražiti uzorak u tekstu.

Primjer

Razmotrimo tekst: "ababcababcabcabc" i uzorak: "abc"

1. Počnite od pozicije 0. Usporedite "a" s prvim znakom "a" u uzorku.
2. Podudaranje pronađeno, prijeđite na sljedeće znakove: "b" s "b" i "a" s "c".
3. Nastavite spajati: "b" s "a", "a" s "b" i "b" s "c".
4. Podudaranje nije uspjelo na poziciji 2.
5. Počnite ponovno od pozicije 3. Usporedite "a" s prvim znakom "a" u uzorku.
6. Uspješno podudaranje: "a" s "a", "b" s "b" i "c" s "c".
7. Snimite poziciju 3.

Uzorak "abc" nalazi se na pozicijama 0, 6 i 9.

Primjer koda u 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;  
}  

U ovom primjeru, stringSearch funkcija se koristi za pronalaženje pojavljivanja uzorka "abc" unutar teksta "ababcababcabcabc". Rezultat će biti vektor koji sadrži početne pozicije utakmica.