Algorytm wyszukiwania ciągów (String Search) w C++- wyjaśnienie, przykład i kod

Algorytm wyszukiwania ciągów służy do znajdowania wystąpień określonego wzorca(podciągu) w większym tekście(łańcuchu). Algorytm ten odgrywa kluczową rolę w zadaniach przetwarzania, wyszukiwania i manipulacji tekstem.

Jak to działa

1. Zacznij od tekstu(ciągu) i wzorca(podciągu), który chcesz wyszukać.
2. Przejrzyj tekst po jednym znaku na raz.
3. Dla każdego znaku w tekście porównaj go z pierwszym znakiem wzorca.
4. Jeśli występuje dopasowanie, sprawdź, czy kolejne znaki również pasują do wzorca.
5. Jeśli wzór jest całkowicie dopasowany, zapisz pozycję początkową dopasowania.
6. Kontynuuj wyszukiwanie wzoru w tekście.

Przykład

Rozważ tekst: „ababcababcabcabc” i wzór: „abc”

1. Zacznij od pozycji 0. Porównaj „a” z pierwszym znakiem „a” we wzorze.
2. Znaleziono dopasowanie, przejdź do kolejnych znaków: „b” z „b” i „a” z „c”.
3. Kontynuuj dopasowywanie: „b” z „a”, „a” z „b” i „b” z „c”.
4. Mecz nie powiódł się na pozycji 2.
5. Zacznij ponownie od pozycji 3. Porównaj „a” z pierwszym znakiem „a” we wzorze.
6. Udane dopasowanie: „a” z „a”, „b” z „b” i „c” z „c”.
7. Rekordowa pozycja 3.

Wzór „abc” znajduje się w pozycjach 0, 6 i 9.

Przykładowy kod w 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;  
}  

W tym przykładzie stringSearch funkcja służy do znajdowania wystąpień wzorca „abc” w tekście „ababcababcabcabc”. Wynikiem będzie wektor zawierający początkowe pozycje meczów.