Tekstsøkealgoritme (Text Search) i C++- Forklaring, eksempel og kode

Tekstsøk-algoritmen er en grunnleggende metode i tekstbehandling og informasjonsinnhenting. Denne algoritmen lar oss lokalisere og identifisere forekomster av en delstreng(eller mønster) i et større stykke tekst.

Hvordan det fungerer

1. Start med et større stykke tekst(eller dokument) og en delstreng å søke etter.
2. Iterér gjennom hvert tegn i teksten sekvensielt.
3. Sammenlign delstrengen med en del av teksten som har samme lengde som delstrengen. Hvis en match blir funnet, registrer gjeldende posisjon.
4. Gå til neste posisjon og fortsett sammenligningen.

Eksempel

Tenk på teksten: "La oss søke etter en delstreng i denne teksten for å se hvordan algoritmen fungerer."

Og understrengen å søke etter: "understreng"

1. Start på posisjon 0. Sammenlign Let' med "delstreng". Ingen treff.
2. Flytt til posisjon 1. Sammenlign et's med "delstreng". Ingen treff.
3. Flytt til posisjon 2. Sammenlign t's " med "understreng". Ingen samsvar.
4. Flytt til posisjon 3. Sammenlign 's s med "delstreng". Ingen treff.
5. Flytt til posisjon 4. Sammenlign se med "understreng". Ingen treff.
6. Flytt til posisjon 5. Sammenlign sea med "delstreng". Ingen treff.
7. Flytt til posisjon 6. Sammenlign earc med "understreng". Ingen treff.
8. Flytt til posisjon 7. Sammenlign arch med "understreng". Ingen treff.
9. Flytt til posisjon 8. Sammenlign rch " med "delstreng". Ingen samsvar.
10. Flytt til posisjon 9. Sammenlign ch w med "understreng". Ingen treff.
11. Flytt til posisjon 10. Sammenlign h wi med "understreng". Ingen treff.
12. Flytt til posisjon 11. Sammenlign " wit med "understreng". Ingen samsvar.
13. Flytt til posisjon 12. Sammenlign with med "understreng". Ingen treff.
14. Flytt til posisjon 13. Sammenlign ithi med "delstreng". Ingen treff.
15. Flytt til posisjon 14. Sammenlign thin med "understreng". Ingen treff.
16. Flytt til posisjon 15. Sammenlign hinn med "understreng". Ingen treff.
17. Flytt til posisjon 16. Sammenlign in t med "understreng". Ingen treff.
18. Flytt til posisjon 17. Sammenlign n th med "understreng". Ingen treff.
19. Flytt til posisjon 18. Sammenlign " thi med "understreng". Ingen samsvar.
20. Flytt til posisjon 19. Sammenlign this med "delstreng". Ingen treff.
21. Flytt til posisjon 20. Sammenlign his " med "delstreng". Ingen samsvar.
22. Flytt til posisjon 21. Sammenlign is t med "understreng". Ingen treff.
23. Flytt til posisjon 22. Sammenlign s te  med "delstreng". Ingen treff.
24. Flytt til posisjon 23. Sammenlign ubst  med "understreng". Ingen treff.
25. Flytt til posisjon 24. Sammenlign bstr med "delstreng". Ingen treff.
26. Flytt til posisjon 25. Sammenlign stre med "delstreng". Ingen treff.
27. Flytt til posisjon 26. Sammenlign trin  med "delstreng". Ingen treff.
28. Flytt til posisjon 27. Sammenlign ring  med "understreng". Kamp funnet, rekordposisjon 27.

Delstrengen "understreng" finnes i posisjon 27 i teksten.

Eksempelkode i 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;  
}  

I dette eksemplet textSearch brukes funksjonen til å finne posisjonene til understrengen "understreng" i teksten. Resultatet vil være en vektor som inneholder startposisjonene til kampene.