close

Textsökningsalgoritm (Text Search) i C++- Förklaring, exempel och kod

Textsökningsalgoritmen är en grundläggande metod för textbearbetning och informationssökning. Denna algoritm tillåter oss att lokalisera och identifiera förekomster av en delsträng(eller mönster) i en större textbit.

Hur det fungerar

  1. Börja med en större bit text(eller dokument) och en delsträng att söka efter.
  2. Iterera genom varje tecken i texten sekventiellt.
  3. Jämför delsträngen med en del av texten som har samma längd som delsträngen. Om en matchning hittas, registrera den aktuella positionen.
  4. Flytta till nästa position och fortsätt jämförelsen.

Exempel

Tänk på texten: "Låt oss söka efter en delsträng i den här texten för att se hur algoritmen fungerar."

Och delsträngen att söka efter: "delsträng"

  1. Börja vid position 0. Jämför Let' med "delsträng". Ingen match.
  2. Flytta till position 1. Jämför et's med "delsträng". Ingen match.
  3. Flytta till position 2. Jämför t's " med "delsträng". Ingen matchning.
  4. Flytta till position 3. Jämför 's s med "delsträng". Ingen match.
  5. Flytta till position 4. Jämför se med "delsträng". Ingen match.
  6. Flytta till position 5. Jämför sea med "delsträng". Ingen match.
  7. Flytta till position 6. Jämför earc med "delsträng". Ingen match.
  8. Flytta till position 7. Jämför arch med "delsträng". Ingen match.
  9. Flytta till position 8. Jämför rch " med "delsträng". Ingen matchning.
  10. Flytta till position 9. Jämför ch w med "delsträng". Ingen match.
  11. Flytta till position 10. Jämför h wi med "delsträng". Ingen match.
  12. Flytta till position 11. Jämför " wit med "delsträng". Ingen matchning.
  13. Flytta till position 12. Jämför with med "delsträng". Ingen match.
  14. Flytta till position 13. Jämför ithi med "delsträng". Ingen match.
  15. Flytta till position 14. Jämför thin med "delsträng". Ingen match.
  16. Flytta till position 15. Jämför hinn med "delsträng". Ingen match.
  17. Flytta till position 16. Jämför in t med "delsträng". Ingen match.
  18. Flytta till position 17. Jämför n th med "delsträng". Ingen match.
  19. Flytta till position 18. Jämför " thi med "delsträng". Ingen matchning.
  20. Flytta till position 19. Jämför this med "delsträng". Ingen match.
  21. Flytta till position 20. Jämför his " med "delsträng". Ingen matchning.
  22. Flytta till position 21. Jämför is t med "delsträng". Ingen match.
  23. Flytta till position 22. Jämför s te  med "delsträng". Ingen match.
  24. Flytta till position 23. Jämför ubst  med "delsträng". Ingen match.
  25. Flytta till position 24. Jämför bstr med "delsträng". Ingen match.
  26. Flytta till position 25. Jämför stre med "delsträng". Ingen match.
  27. Flytta till position 26. Jämför trin  med "delsträng". Ingen match.
  28. Flytta till position 27. Jämför ring  med "delsträng". Match hittad, rekordposition 27.

Delsträngen "delsträng" finns vid position 27 i texten.

Exempelkod 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 det här exemplet textSearch används funktionen för att hitta positionerna för delsträngen "delsträng" i texten. Resultatet blir en vektor som innehåller startpositionerna för matcherna.