close

Algoritmo di ricerca testuale (Text Search) in C++- Spiegazione, esempio e codice

L'algoritmo di ricerca del testo è un metodo fondamentale nell'elaborazione del testo e nel recupero delle informazioni. Questo algoritmo ci consente di individuare e identificare le occorrenze di una sottostringa(o modello) all'interno di una parte di testo più ampia.

Come funziona

  1. Inizia con una parte di testo(o documento) più grande e una sottostringa da cercare.
  2. Itera attraverso ogni carattere del testo in sequenza.
  3. Confronta la sottostringa con una parte del testo che ha la stessa lunghezza della sottostringa. Se viene trovata una corrispondenza, registrare la posizione corrente.
  4. Passa alla posizione successiva e continua il confronto.

Esempio

Considera il testo: "Cerchiamo una sottostringa all'interno di questo testo per vedere come funziona l'algoritmo".

E la sottostringa da cercare: "sottostringa"

  1. Inizia dalla posizione 0. Confronta Let' con "sottostringa". Nessuna corrispondenza.
  2. Passa alla posizione 1. Confronta et's con "sottostringa". Nessuna corrispondenza.
  3. Passa alla posizione 2. Confronta t's " con "sottostringa". Nessuna corrispondenza.
  4. Passa alla posizione 3. Confronta 's s con "sottostringa". Nessuna corrispondenza.
  5. Passa alla posizione 4. Confronta se con "sottostringa". Nessuna corrispondenza.
  6. Passa alla posizione 5. Confronta sea con "sottostringa". Nessuna corrispondenza.
  7. Passa alla posizione 6. Confronta earc con "sottostringa". Nessuna corrispondenza.
  8. Passa alla posizione 7. Confronta arch con "sottostringa". Nessuna corrispondenza.
  9. Passa alla posizione 8. Confronta rch " con "sottostringa". Nessuna corrispondenza.
  10. Passa alla posizione 9. Confronta ch w con "sottostringa". Nessuna corrispondenza.
  11. Passa alla posizione 10. Confronta h wi con "sottostringa". Nessuna corrispondenza.
  12. Passa alla posizione 11. Confronta " wit con "sottostringa". Nessuna corrispondenza.
  13. Passa alla posizione 12. Confronta with con "sottostringa". Nessuna corrispondenza.
  14. Passa alla posizione 13. Confronta ithi con "sottostringa". Nessuna corrispondenza.
  15. Passa alla posizione 14. Confronta thin con "sottostringa". Nessuna corrispondenza.
  16. Passa alla posizione 15. Confronta hinn con "sottostringa". Nessuna corrispondenza.
  17. Passa alla posizione 16. Confronta in t con "sottostringa". Nessuna corrispondenza.
  18. Passa alla posizione 17. Confronta n th con "sottostringa". Nessuna corrispondenza.
  19. Passa alla posizione 18. Confronta " thi con "sottostringa". Nessuna corrispondenza.
  20. Passa alla posizione 19. Confronta this con "sottostringa". Nessuna corrispondenza.
  21. Passa alla posizione 20. Confronta his " con "sottostringa". Nessuna corrispondenza.
  22. Passa alla posizione 21. Confronta is t con "sottostringa". Nessuna corrispondenza.
  23. Passa alla posizione 22. Confronta s te  con "sottostringa". Nessuna corrispondenza.
  24. Passa alla posizione 23. Confronta ubst  con "sottostringa". Nessuna corrispondenza.
  25. Passa alla posizione 24. Confronta bstr con "sottostringa". Nessuna corrispondenza.
  26. Passa alla posizione 25. Confronta stre con "sottostringa". Nessuna corrispondenza.
  27. Passa alla posizione 26. Confronta trin  con "sottostringa". Nessuna corrispondenza.
  28. Passa alla posizione 27. Confronta ring  con "sottostringa". Partita trovata, posizione record 27.

La sottostringa "substring" si trova alla posizione 27 all'interno del testo.

Esempio di codice 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 questo esempio, la textSearch funzione viene utilizzata per trovare le posizioni della sottostringa "sottostringa" all'interno del testo. Il risultato sarà un vettore contenente le posizioni di partenza delle partite.