Algoritm de căutare text (Text Search) în C++- Explicație, Exemplu și Cod

Algoritmul de căutare text este o metodă fundamentală în procesarea textului și regăsirea informațiilor. Acest algoritm ne permite să localizăm și să identificăm aparițiile unui subșir(sau model) într-o bucată mai mare de text.

Cum functioneaza

1. Începeți cu o bucată mai mare de text(sau document) și un subșir de căutat.
2. Repetați fiecare caracter al textului succesiv.
3. Comparați subșirul cu o porțiune a textului care are aceeași lungime ca și subșirul. Dacă se găsește o potrivire, înregistrați poziția curentă.
4. Treceți la următoarea poziție și continuați comparația.

Exemplu

Luați în considerare textul: „Să căutăm un subșir în acest text pentru a vedea cum funcționează algoritmul”.

Și subșirul de căutat: „subșir”

1. Începeți de la poziția 0. Comparați Let' cu „subșir”. Nu se potrivesc.
2. Treceți în poziția 1. Comparați et's cu „subșir”. Nu se potrivesc.
3. Mutați-vă în poziția 2. Comparați t's „ cu „subșir”. Nu se potrivește.
4. Treceți în poziția 3. Comparați 's s cu „subșir”. Nu se potrivesc.
5. Treceți în poziția 4. Comparați se cu „subșir”. Nu se potrivesc.
6. Deplasați-vă în poziția 5. Comparați sea cu „subșir”. Nu se potrivesc.
7. Treceți în poziția 6. Comparați earc cu „subșir”. Nu se potrivesc.
8. Treceți în poziția 7. Comparați arch cu „subșir”. Nu se potrivesc.
9. Mutați-vă în poziția 8. Comparați rch „ cu „subșir”. Nu se potrivește.
10. Treceți în poziția 9. Comparați ch w cu „subșir”. Nu se potrivesc.
11. Mutați-vă în poziția 10. Comparați h wi cu „subșir”. Nu se potrivesc.
12. Mutați-vă în poziția 11. Comparați „ wit cu „subșir”. Nu se potrivește.
13. Mutați-vă în poziția 12. Comparați with cu „subșir”. Nu se potrivesc.
14. Mutați-vă în poziția 13. Comparați ithi cu „subșir”. Nu se potrivesc.
15. Mutați-vă în poziția 14. Comparați thin cu „subșir”. Nu se potrivesc.
16. Mutați-vă în poziția 15. Comparați hinn cu „subșir”. Nu se potrivesc.
17. Mutați-vă în poziția 16. Comparați in t cu „subșir”. Nu se potrivesc.
18. Treceți la poziția 17. Comparați n th cu „subșir”. Nu se potrivesc.
19. Mutați-vă în poziția 18. Comparați „ thi cu „subșir”. Nu se potrivește.
20. Mutați-vă în poziția 19. Comparați this cu „subșir”. Nu se potrivesc.
21. Mutați-vă în poziția 20. Comparați his „ cu „subșir”. Nu se potrivește.
22. Mutați-vă în poziția 21. Comparați is t cu „subșir”. Nu se potrivesc.
23. Mutați-vă în poziția 22. Comparați s te  cu „subșir”. Nu se potrivesc.
24. Mutați-vă în poziția 23. Comparați ubst  cu „subșir”. Nu se potrivesc.
25. Mutați-vă în poziția 24. Comparați bstr cu „subșir”. Nu se potrivesc.
26. Mutați-vă în poziția 25. Comparați stre cu „subșir”. Nu se potrivesc.
27. Mutați-vă în poziția 26. Comparați trin  cu „subșir”. Nu se potrivesc.
28. Mutați-vă în poziția 27. Comparați ring  cu „subșir”. Meci găsit, poziția record 27.

Subșirul „subșir” se găsește la poziția 27 în text.

Exemplu de cod în 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;  
}  

În acest exemplu, textSearch funcția este folosită pentru a găsi pozițiile subșirului „subșir” în text. Rezultatul va fi un vector care conține pozițiile de început ale meciurilor.