Teksto paieškos (Text Search) algoritmas C++ – paaiškinimas, pavyzdys ir kodas

Teksto paieškos algoritmas yra pagrindinis teksto apdorojimo ir informacijos gavimo metodas. Šis algoritmas leidžia mums rasti ir nustatyti poeilutės(arba šablono) atvejus didesnėje teksto dalyje.

Kaip tai veikia

1. Pradėkite nuo didesnės teksto dalies(arba dokumento) ir ieškomos poeilutės.
2. Pakartokite kiekvieną teksto simbolį iš eilės.
3. Palyginkite eilutę su teksto dalimi, kurios ilgis yra toks pat, kaip ir poeilutė. Jei randama atitiktis, užrašykite dabartinę padėtį.
4. Pereikite į kitą poziciją ir tęskite palyginimą.

Pavyzdys

Apsvarstykite tekstą: „Ieškokime poeilutės šiame tekste, kad pamatytume, kaip veikia algoritmas“.

Ir poeilutė, kurios reikia ieškoti: "substring"

1. Pradėkite nuo 0 pozicijos. Palyginkite Let' su "substyle". Jokio atitikmens.
2. Perkelkite į 1 padėtį. Palyginkite et's su „substyle“. Jokio atitikmens.
3. Perkelkite į 2 padėtį. Palyginkite t's " su "substyling". Nėra atitikties.
4. Perkelkite į 3 padėtį. Palyginkite 's s su „substyle“. Jokio atitikmens.
5. Perkelkite į 4 poziciją. Palyginkite se su "substyle". Jokio atitikmens.
6. Perkelkite į 5 padėtį. Palyginkite sea su "substyle". Jokio atitikmens.
7. Perkelkite į 6 poziciją. Palyginkite earc su „substyle“. Jokio atitikmens.
8. Perkelkite į 7 poziciją. Palyginkite arch su "substyle". Jokio atitikmens.
9. Perkelkite į 8 poziciją. Palyginkite rch " su "substyling". Atitikties nėra.
10. Perkelkite į 9 poziciją. Palyginkite ch w su "substyle". Jokio atitikmens.
11. Perkelkite į 10 padėtį. Palyginkite h wi su „substyle“. Jokio atitikmens.
12. Perkelkite į 11 poziciją. Palyginkite " wit su "substyling". Atitikties nėra.
13. Perkelkite į 12 poziciją. Palyginkite with su "substyle". Jokio atitikmens.
14. Perkelkite į 13 padėtį. Palyginkite ithi su "substyle". Jokio atitikmens.
15. Perkelkite į 14 poziciją. Palyginkite thin su "substyle". Jokio atitikmens.
16. Perkelkite į 15 poziciją. Palyginkite hinn su "substyle". Jokio atitikmens.
17. Perkelkite į 16 poziciją. Palyginkite in t su "substyle". Jokio atitikmens.
18. Perkelkite į 17 poziciją. Palyginkite n th su "substyle". Jokio atitikmens.
19. Perkelkite į 18 poziciją. Palyginkite " thi su "substyling". Atitikties nėra.
20. Perkelkite į 19 poziciją. Palyginkite this su "substyle". Jokio atitikmens.
21. Perkelkite į 20 poziciją. Palyginkite his " su "substyling". Nėra atitikties.
22. Perkelkite į 21 poziciją. Palyginkite is t su "substyle". Jokio atitikmens.
23. Perkelkite į 22 poziciją. Palyginkite s te  su "substyle". Jokio atitikmens.
24. Perkelkite į 23 poziciją. Palyginkite ubst  su "substyle". Jokio atitikmens.
25. Perkelkite į 24 poziciją. Palyginkite bstr su "substyle". Jokio atitikmens.
26. Perkelkite į 25 poziciją. Palyginkite stre su "substyle". Jokio atitikmens.
27. Perkelkite į 26 poziciją. Palyginkite trin  su "substyle". Jokio atitikmens.
28. Perkelkite į 27 poziciją. Palyginkite ring  su "substyle". Rungtynės rastas, rekordinė 27 vieta.

Poeilutė „poeilutė“ yra 27 teksto pozicijoje.

Kodo pavyzdys C++

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

Šiame pavyzdyje textSearch funkcija naudojama norint rasti poeilutės „substyling“ vietas tekste. Rezultatas bus vektorius, kuriame yra rungtynių pradinės pozicijos.