Tekstzoekalgoritme (Text Search) in C ++- uitleg, voorbeeld en code

Het tekstzoekalgoritme is een fundamentele methode bij het verwerken van tekst en het ophalen van informatie. Met dit algoritme kunnen we voorkomens van een subtekenreeks(of patroon) binnen een groter stuk tekst lokaliseren en identificeren.

Hoe het werkt

1. Begin met een groter stuk tekst(of document) en een substring om naar te zoeken.
2. Doorloop elk teken van de tekst opeenvolgend.
3. Vergelijk de subtekenreeks met een deel van de tekst dat dezelfde lengte heeft als de subtekenreeks. Als er een overeenkomst is gevonden, noteert u de huidige positie.
4. Ga naar de volgende positie en ga verder met de vergelijking.

Voorbeeld

Beschouw de tekst: "Laten we zoeken naar een subtekenreeks in deze tekst om te zien hoe het algoritme werkt."

En de substring om naar te zoeken: "substring"

1. Begin op positie 0. Vergelijk Let' met "substring". Geen match.
2. Ga naar positie 1. Vergelijk et's met "substring". Geen match.
3. Ga naar positie 2. Vergelijk t's " met "subtekenreeks". Geen overeenkomst.
4. Ga naar positie 3. Vergelijk 's s met "substring". Geen match.
5. Ga naar positie 4. Vergelijk se met "substring". Geen match.
6. Ga naar positie 5. Vergelijk sea met "substring". Geen match.
7. Ga naar positie 6. Vergelijk earc met "substring". Geen match.
8. Ga naar positie 7. Vergelijk arch met "substring". Geen match.
9. Ga naar positie 8. Vergelijk rch " met "subtekenreeks". Geen overeenkomst.
10. Ga naar positie 9. Vergelijk ch w met "substring". Geen match.
11. Ga naar positie 10. Vergelijk h wi met "substring". Geen match.
12. Ga naar positie 11. Vergelijk " wit met "subtekenreeks". Geen overeenkomst.
13. Ga naar positie 12. Vergelijk with met "substring". Geen match.
14. Ga naar positie 13. Vergelijk ithi met "substring". Geen match.
15. Ga naar positie 14. Vergelijk thin met "substring". Geen match.
16. Ga naar positie 15. Vergelijk hinn met "substring". Geen match.
17. Ga naar positie 16. Vergelijk in t met "substring". Geen match.
18. Ga naar positie 17. Vergelijk n th met "substring". Geen match.
19. Ga naar positie 18. Vergelijk " thi met "subtekenreeks". Geen overeenkomst.
20. Ga naar positie 19. Vergelijk this met "substring". Geen match.
21. Ga naar positie 20. Vergelijk his " met "subtekenreeks". Geen overeenkomst.
22. Ga naar positie 21. Vergelijk is t met "substring". Geen match.
23. Ga naar positie 22. Vergelijk s te  met "substring". Geen match.
24. Ga naar positie 23. Vergelijk ubst  met "substring". Geen match.
25. Ga naar positie 24. Vergelijk bstr met "substring". Geen match.
26. Ga naar positie 25. Vergelijk stre met "substring". Geen match.
27. Ga naar positie 26. Vergelijk trin  met "substring". Geen match.
28. Ga naar positie 27. Vergelijk ring  met "substring". Match gevonden, recordpositie 27.

De subtekenreeks "subtekenreeks" bevindt zich op positie 27 in de tekst.

Voorbeeldcode in 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;  
}  

In dit voorbeeld textSearch wordt de functie gebruikt om de posities van de subtekenreeks "subtekenreeks" in de tekst te vinden. Het resultaat is een vector met daarin de startposities van de wedstrijden.