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

Algoritmul de căutare de șiruri este utilizat pentru a găsi aparițiile unui anumit model(subșir) într-un text mai mare(șir). Acest algoritm joacă un rol crucial în procesarea textului, căutarea și sarcinile de manipulare.

Cum functioneaza

1. Începeți cu un text(șir) și un model(subșir) de căutat.
2. Repetați textul câte un caracter.
3. Pentru fiecare caracter din text, comparați-l cu primul caracter al modelului.
4. Dacă există o potrivire, verificați dacă și caracterele ulterioare se potrivesc cu modelul.
5. Dacă modelul este complet potrivit, înregistrați poziția de început a meciului.
6. Continuați să căutați modelul în text.

Exemplu

Luați în considerare un text: „ababcababcabcabc” și un model: „abc”

1. Începeți de la poziția 0. Comparați „a” cu primul caracter „a” din model.
2. Potrivire găsită, treceți la următoarele caractere: „b” cu „b” și „a” cu „c”.
3. Continuați potrivirea: „b” cu „a”, „a” cu „b” și „b” cu „c”.
4. Meciul a eșuat la poziția 2.
5. Începeți din nou de la poziția 3. Comparați „a” cu primul caracter „a” din model.
6. Potrivire reușită: „a” cu „a”, „b” cu „b” și „c” cu „c”.
7. Poziția de înregistrare 3.

Modelul „abc” se găsește la pozițiile 0, 6 și 9.

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

În acest exemplu, stringSearch funcția este utilizată pentru a găsi aparițiile modelului „abc” în textul „ababcababcabcabc”. Rezultatul va fi un vector care conține pozițiile de început ale meciurilor.