Tekstihakualgoritmi (Text Search) C++:ssa- selitys, esimerkki ja koodi

Tekstihakualgoritmi on perusmenetelmä tekstinkäsittelyssä ja tiedonhaussa. Tämän algoritmin avulla voimme paikantaa ja tunnistaa alimerkkijonon(tai kuvion) ​​esiintymät suuremmassa tekstissä.

Kuinka se toimii

1. Aloita suuremmalla tekstinpalalla(tai asiakirjalla) ja haettavalla alimerkkijonolla.
2. Toista tekstin jokainen merkki peräkkäin.
3. Vertaa osamerkkijonoa tekstin osaan, jonka pituus on sama kuin alimerkkijono. Jos vastaavuus löytyy, tallenna nykyinen sijainti.
4. Siirry seuraavaan kohtaan ja jatka vertailua.

Esimerkki

Harkitse tekstiä: "Etsitään tästä tekstistä alimerkkijonoa nähdäksemme, kuinka algoritmi toimii."

Ja etsittävä alimerkkijono: "alimerkkijono"

1. Aloita paikasta 0. Vertaa Let' "alimerkkijonoon". Ei osumia.
2. Siirry kohtaan 1. Vertaa et's "alimerkkijonoon". Ei osumia.
3. Siirry kohtaan 2. Vertaa t's " ja "alimerkkijono". Ei vastaavuutta.
4. Siirry kohtaan 3. Vertaa 's s "alimerkkijonoon". Ei osumia.
5. Siirry kohtaan 4. Vertaa se "alimerkkijonoon". Ei osumia.
6. Siirry kohtaan 5. Vertaa sea "alimerkkijonoon". Ei osumia.
7. Siirry kohtaan 6. Vertaa earc "alimerkkijonoon". Ei osumia.
8. Siirry kohtaan 7. Vertaa arch "alimerkkijonoon". Ei osumia.
9. Siirry kohtaan 8. Vertaa rch " ja "alimerkkijono". Ei vastaavuutta.
10. Siirry kohtaan 9. Vertaa ch w "alimerkkijonoon". Ei osumia.
11. Siirry kohtaan 10. Vertaa h wi "alimerkkijonoon". Ei osumia.
12. Siirry kohtaan 11. Vertaa " wit ja "alimerkkijono". Ei vastaavuutta.
13. Siirry kohtaan 12. Vertaa with "alimerkkijonoon". Ei osumia.
14. Siirry kohtaan 13. Vertaa ithi "alimerkkijonoon". Ei osumia.
15. Siirry kohtaan 14. Vertaa thin "alimerkkijonoon". Ei osumia.
16. Siirry kohtaan 15. Vertaa hinn "alimerkkijonoon". Ei osumia.
17. Siirry kohtaan 16. Vertaa in t "alimerkkijonoon". Ei osumia.
18. Siirry kohtaan 17. Vertaa n th "alimerkkijonoon". Ei osumia.
19. Siirry kohtaan 18. Vertaa " thi ja "alimerkkijono". Ei vastaavuutta.
20. Siirry kohtaan 19. Vertaa this "alimerkkijonoon". Ei osumia.
21. Siirry kohtaan 20. Vertaa his " ja "alimerkkijono". Ei vastaavuutta.
22. Siirry kohtaan 21. Vertaa is t "alimerkkijonoon". Ei osumia.
23. Siirry kohtaan 22. Vertaa s te  "alimerkkijonoon". Ei osumia.
24. Siirry kohtaan 23. Vertaa ubst  "alimerkkijonoon". Ei osumia.
25. Siirry kohtaan 24. Vertaa bstr "alimerkkijonoon". Ei osumia.
26. Siirry kohtaan 25. Vertaa stre "alimerkkijonoon". Ei osumia.
27. Siirry kohtaan 26. Vertaa trin  "alimerkkijonoon". Ei osumia.
28. Siirry kohtaan 27. Vertaa ring  "alimerkkijonoon". Ottelu löydetty, ennätyssijainti 27.

Osamerkkijono "alimerkkijono" löytyy tekstin kohdasta 27.

Esimerkkikoodi C++:ssa

#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;  
}  

Tässä esimerkissä funktiota textSearch käytetään etsimään alimerkkijonon "alimerkkijono" paikat tekstistä. Tuloksena on vektori, joka sisältää otteluiden aloituspaikat.