Szövegkereső (Text Search) algoritmus C++ nyelven – magyarázat, példa és kód

A szövegkereső algoritmus a szövegfeldolgozás és információ-visszakeresés alapvető módszere. Ez az algoritmus lehetővé teszi számunkra, hogy megkeressük és azonosítsuk egy részkarakterlánc(vagy minta) előfordulásait egy nagyobb szövegrészen belül.

Hogyan működik

1. Kezdje egy nagyobb szövegrészlettel(vagy dokumentummal) és a keresendő részkarakterlánccal.
2. Iteráld végig a szöveg minden karakterét egymás után.
3. Hasonlítsa össze az alkarakterláncot a szöveg egy részével, amelynek hossza megegyezik az alkarakterlánccal. Ha talál egyezést, rögzítse az aktuális pozíciót.
4. Lépjen a következő pozícióra, és folytassa az összehasonlítást.

Példa

Fontolja meg a szöveget: "Keressünk egy részkarakterláncot ebben a szövegben, hogy lássuk, hogyan működik az algoritmus."

És a keresendő részkarakterlánc: "substring"

1. Kezdje a 0. pozícióban. Hasonlítsa össze Let' az "alkarakterlánccal". Nem egyezik.
2. Lépjen az 1. pozícióba. Hasonlítsa össze et's az "alkarakterlánccal". Nem egyezik.
3. Lépjen a 2. pozícióba. Hasonlítsa össze t's a " karakterláncot " az "alkarakterlánccal". Nincs egyezés.
4. Lépjen a 3. pozícióba. Hasonlítsa össze 's s az "alkarakterlánccal". Nem egyezik.
5. Lépjen a 4. pozícióba. Hasonlítsa össze se az "alkarakterlánccal". Nem egyezik.
6. Lépjen az 5. pozícióba. Hasonlítsa össze sea az "alkarakterlánccal". Nem egyezik.
7. Lépjen a 6. pozícióba. Hasonlítsa össze earc az "alkarakterlánccal". Nem egyezik.
8. Lépjen a 7. pozícióba. Hasonlítsa össze arch az "alkarakterlánccal". Nem egyezik.
9. Lépjen a 8. pozícióba. Hasonlítsa össze rch a " részt az "alkarakterlánccal". Nincs egyezés.
10. Lépjen a 9. pozícióba. Hasonlítsa össze ch w az "alkarakterlánccal". Nem egyezik.
11. Lépjen a 10. pozícióba. Hasonlítsa össze h wi az "alkarakterlánccal". Nem egyezik.
12. Lépjen a 11. pozícióba. Hasonlítsa össze a " wit részt az "alkarakterlánccal". Nincs egyezés.
13. Lépjen a 12. pozícióba. Hasonlítsa össze with az "alkarakterlánccal". Nem egyezik.
14. Lépjen a 13. pozícióba. Hasonlítsa össze ithi az "alkarakterlánccal". Nem egyezik.
15. Lépjen a 14. pozícióba. Hasonlítsa össze thin az "alkarakterlánccal". Nem egyezik.
16. Lépjen a 15. pozícióba. Hasonlítsa össze hinn az "alkarakterlánccal". Nem egyezik.
17. Lépjen a 16. pozícióba. Hasonlítsa össze in t az "alkarakterlánccal". Nem egyezik.
18. Lépjen a 17. pozícióba. Hasonlítsa össze n th az "alkarakterlánccal". Nem egyezik.
19. Lépjen a 18. pozícióba. Hasonlítsa össze a " thi részt az "alkarakterlánccal". Nincs egyezés.
20. Lépjen a 19. pozícióba. Hasonlítsa össze this az "alkarakterlánccal". Nem egyezik.
21. Lépjen a 20. pozícióba. Hasonlítsa össze his a " részt az "alkarakterlánccal". Nincs egyezés.
22. Lépjen a 21. pozícióba. Hasonlítsa össze is t az "alkarakterlánccal". Nem egyezik.
23. Lépjen a 22. pozícióba. Hasonlítsa össze s te  az "alkarakterlánccal". Nem egyezik.
24. Lépjen a 23. pozícióba. Hasonlítsa össze ubst  az "alkarakterlánccal". Nem egyezik.
25. Lépjen a 24. pozícióba. Hasonlítsa össze bstr az "alkarakterlánccal". Nem egyezik.
26. Lépjen a 25. pozícióba. Hasonlítsa össze stre az "alkarakterlánccal". Nem egyezik.
27. Lépjen a 26. pozícióba. Hasonlítsa össze trin  az "alkarakterlánccal". Nem egyezik.
28. Lépjen a 27. pozícióba. Hasonlítsa össze ring  az "alkarakterlánccal". Talált egyezést, rekordpozíció 27.

Az "alkarakterlánc" a szöveg 27. pozíciójában található.

Példakód C++ nyelven

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Ebben a példában a textSearch függvény a "substring" részkarakterlánc pozícióinak megkeresésére szolgál a szövegben. Az eredmény egy vektor lesz, amely a mérkőzések kezdőpontjait tartalmazza.