close

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

Tekstsøgningsalgoritmen er en grundlæggende metode til tekstbehandling og informationssøgning. Denne algoritme giver os mulighed for at lokalisere og identificere forekomster af en understreng(eller et mønster) i et større stykke tekst.

Hvordan det virker

  1. Start med et større stykke tekst(eller dokument) og en understreng at søge efter.
  2. Gentag gennem hvert tegn i teksten sekventielt.
  3. Sammenlign understrengen med en del af teksten, der har samme længde som understrengen. Hvis der findes et match, skal du registrere den aktuelle position.
  4. Flyt til næste position og fortsæt sammenligningen.

Eksempel

Overvej teksten: "Lad os søge efter en understreng i denne tekst for at se, hvordan algoritmen fungerer."

Og understrengen, der skal søges efter: "understreng"

  1. Start ved position 0. Sammenlign Let' med "understreng". Intet match.
  2. Flyt til position 1. Sammenlign et's med "understreng". Intet match.
  3. Flyt til position 2. Sammenlign t's " med "understreng". Ingen match.
  4. Flyt til position 3. Sammenlign 's s med "understreng". Intet match.
  5. Flyt til position 4. Sammenlign se med "understreng". Intet match.
  6. Flyt til position 5. Sammenlign sea med "understreng". Intet match.
  7. Flyt til position 6. Sammenlign earc med "understreng". Intet match.
  8. Flyt til position 7. Sammenlign arch med "understreng". Intet match.
  9. Flyt til position 8. Sammenlign rch " med "understreng". Ingen match.
  10. Flyt til position 9. Sammenlign ch w med "understreng". Intet match.
  11. Flyt til position 10. Sammenlign h wi med "understreng". Intet match.
  12. Flyt til position 11. Sammenlign " wit med "understreng". Ingen match.
  13. Flyt til position 12. Sammenlign with med "understreng". Intet match.
  14. Flyt til position 13. Sammenlign ithi med "understreng". Intet match.
  15. Flyt til position 14. Sammenlign thin med "understreng". Intet match.
  16. Flyt til position 15. Sammenlign hinn med "understreng". Intet match.
  17. Flyt til position 16. Sammenlign in t med "understreng". Intet match.
  18. Flyt til position 17. Sammenlign n th med "understreng". Intet match.
  19. Flyt til position 18. Sammenlign " thi med "understreng". Ingen match.
  20. Flyt til position 19. Sammenlign this med "understreng". Intet match.
  21. Flyt til position 20. Sammenlign his " med "understreng". Ingen match.
  22. Flyt til position 21. Sammenlign is t med "understreng". Intet match.
  23. Flyt til position 22. Sammenlign s te  med "understreng". Intet match.
  24. Flyt til position 23. Sammenlign ubst  med "understreng". Intet match.
  25. Flyt til position 24. Sammenlign bstr med "understreng". Intet match.
  26. Flyt til position 25. Sammenlign stre med "understreng". Intet match.
  27. Flyt til position 26. Sammenlign trin  med "understreng". Intet match.
  28. Flyt til position 27. Sammenlign ring  med "understreng". Match fundet, rekordposition 27.

Understrengen "understreng" findes på position 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 eksempel textSearch bruges funktionen til at finde positionerne af understrengen "understreng" i teksten. Resultatet vil være en vektor, der indeholder startpositionerne for kampene.