Styginių paieškos (String Search) algoritmas C++ kalboje – paaiškinimas, pavyzdys ir kodas

Eilučių paieškos algoritmas naudojamas ieškant konkretaus šablono(poeilutės) atvejų didesniame tekste(eilutė). Šis algoritmas atlieka lemiamą vaidmenį atliekant teksto apdorojimo, paieškos ir manipuliavimo užduotis.

Kaip tai veikia

1. Pradėkite nuo teksto(eilutės) ir šablono(poeilutės), kurio norite ieškoti.
2. Kartokite tekstą po vieną simbolį.
3. Kiekvieną teksto simbolį palyginkite su pirmuoju rašto simboliu.
4. Jei yra atitiktis, patikrinkite, ar tolesni simboliai taip pat atitinka šabloną.
5. Jei modelis visiškai atitinka, užrašykite pradinę rungtynių padėtį.
6. Tęskite šablono paiešką tekste.

Pavyzdys

Apsvarstykite tekstą: „ababcababcabcabc“ ir modelį: „abc“

1. Pradėkite nuo 0 padėties. Palyginkite „a“ su pirmuoju simboliu „a“ šablone.
2. Atitiktis rasta, pereikite prie kitų simbolių: „b“ su „b“ ir „a“ su „c“.
3. Tęskite derinimą: „b“ su „a“, „a“ su „b“ ir „b“ su „c“.
4. Rungtynės nepavyko 2 pozicijoje.
5. Pradėkite iš naujo nuo 3 pozicijos. Palyginkite „a“ su pirmuoju simboliu „a“.
6. Sėkmingos rungtynės: „a“ su „a“, „b“ su „b“ ir „c“ su „c“.
7. 3 įrašo pozicija.

Raštas „abc“ yra 0, 6 ir 9 pozicijose.

Kodo pavyzdys 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;  
}  

Šiame pavyzdyje stringSearch funkcija naudojama šablono „abc“ atvejams rasti tekste „ababcababcabcabc“. Rezultatas bus vektorius, kuriame yra rungtynių pradinės pozicijos.