Algoritmus hledání řetězce (String Search) v C++- vysvětlení, příklad a kód

Algoritmus hledání řetězce se používá k nalezení výskytů určitého vzoru(podřetězce) v rámci většího textu(řetězce). Tento algoritmus hraje klíčovou roli při zpracování, vyhledávání a manipulaci s textem.

Jak to funguje

1. Začněte textem(řetězcem) a vzorem(podřetězcem), který chcete vyhledat.
2. Iterujte textem jeden znak po druhém.
3. Pro každý znak v textu jej porovnejte s prvním znakem vzoru.
4. Pokud existuje shoda, zkontrolujte, zda se následující znaky také shodují se vzorem.
5. Pokud je vzor zcela shodný, zaznamenejte výchozí pozici shody.
6. Pokračujte v hledání vzoru v textu.

Příklad

Zvažte text: "ababcababcabcabc" A vzor: "abc"

1. Začněte na pozici 0. Porovnejte „a“ s prvním znakem „a“ ve vzoru.
2. Shoda nalezena, přejděte na další znaky: "b" s "b" a "a" s "c".
3. Pokračujte ve shodě: "b" s "a", "a" s "b" a "b" s "c".
4. Zápas se nezdařil na pozici 2.
5. Začněte znovu na pozici 3. Porovnejte „a“ s prvním znakem „a“ ve vzoru.
6. Úspěšná shoda: "a" s "a", "b" s "b" a "c" s "c".
7. Pozice záznamu 3.

Vzor "abc" se nachází na pozicích 0, 6 a 9.

Příklad kódu v C++

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

V tomto příkladu stringSearch se funkce používá k nalezení výskytů vzoru "abc" v textu "ababcababcabcabc". Výsledkem bude vektor obsahující počáteční pozice zápasů.