Karakterlánc keresési (String Search) algoritmus C++ nyelven- Magyarázat, példa és kód

A karakterlánc-kereső algoritmus arra szolgál, hogy egy nagyobb szövegen(karakterláncon) belül megkeresse egy adott minta(alkarakterlánc) előfordulásait. Ez az algoritmus döntő szerepet játszik a szövegfeldolgozási, keresési és manipulációs feladatokban.

Hogyan működik

1. Kezdje egy szöveggel(karakterlánc) és egy mintával(alkarakterlánc) a kereséshez.
2. Egyszerre egy karakterrel iteráld végig a szöveget.
3. Hasonlítsa össze a szöveg minden egyes karakterét a minta első karakterével.
4. Ha van egyezés, ellenőrizze, hogy a következő karakterek is egyeznek-e a mintával.
5. Ha a minta teljesen megegyezik, jegyezze fel a gyufa kiindulási helyzetét.
6. Folytassa a minta keresését a szövegben.

Példa

Vegyünk egy szöveget: "ababcababcabcabc" és egy mintát: "abc"

1. Kezdje a 0. pozícióból. Hasonlítsa össze az "a"-t a minta első "a" karakterével.
2. Talált egyezést, lépjen a következő karakterekre: „b” a „b”-vel és „a”-val „c”.
3. Folytassa a párosítást: „b” és „a”, „a” „b”, „b” pedig „c”.
4. A mérkőzés a 2. pozíciónál nem sikerült.
5. Kezdje újra a 3. pozícióban. Hasonlítsa össze az "a"-t a minta első "a" karakterével.
6. Sikeres egyezés: „a” az „a”-val, „b” a „b”-vel és „c” a „c”-vel.
7. Rögzítési pozíció 3.

Az "abc" minta a 0, 6 és 9 pozíciókban található.

Példakód C++ nyelven

#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;  
}  

Ebben a példában a stringSearch függvény az „abc” minta előfordulásait keresi az „ababcababcabcabc” szövegben. Az eredmény egy vektor lesz, amely a mérkőzések kezdőpontjait tartalmazza.