Merkkijonohakualgoritmi (String Search) C++:ssa- selitys, esimerkki ja koodi

Merkkijonohakualgoritmia käytetään tietyn kuvion(osamerkkijonon) esiintymien etsimiseen suuremmasta tekstistä(merkkijonosta). Tällä algoritmilla on ratkaiseva rooli tekstinkäsittely-, haku- ja käsittelytehtävissä.

Kuinka se toimii

1. Aloita etsittävällä tekstillä(merkkijono) ja kuviolla(osamerkkijono).
2. Toista tekstiä yksi merkki kerrallaan.
3. Vertaa jokaista tekstin merkkiä kuvion ensimmäiseen merkkiin.
4. Jos vastaavuus löytyy, tarkista, vastaavatko myös seuraavat merkit kuviota.
5. Jos kuvio on täysin yhteensopiva, kirjaa ottelun aloitussijainti.
6. Jatka kuvion etsimistä tekstistä.

Esimerkki

Harkitse tekstiä: "ababcababcabcabc" ja kuviota: "abc"

1. Aloita paikasta 0. Vertaa "a" kuvion ensimmäiseen merkkiin "a".
2. Vastaavuus löydetty, siirry seuraaviin merkkeihin: "b" ja "b" ja "a" ja "c".
3. Jatka yhdistämistä: "b":llä "a", "a"b":llä ja "b":llä "c".
4. Ottelu epäonnistui sijainnissa 2.
5. Aloita uudelleen kohdasta 3. Vertaa "a" kuvion ensimmäiseen merkkiin "a".
6. Onnistunut ottelu: "a" kirjaimella "a", "b" kirjaimella "b" ja "c" kirjaimella "c".
7. Äänityspaikka 3.

Kuvio "abc" löytyy paikoista 0, 6 ja 9.

Esimerkkikoodi C++:ssa

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Tässä esimerkissä stringSearch funktiota käytetään etsimään kuvion "abc" esiintymiä tekstistä "ababcababcabcabc". Tuloksena on vektori, joka sisältää otteluiden aloituspaikat.