Algoritmo di ricerca di stringhe (String Search) in C++- Spiegazione, esempio e codice

L'algoritmo di ricerca di stringhe viene utilizzato per trovare le occorrenze di un modello specifico(sottostringa) all'interno di un testo più grande(stringa). Questo algoritmo svolge un ruolo cruciale nelle attività di elaborazione, ricerca e manipolazione del testo.

Come funziona

1. Inizia con un testo(stringa) e uno schema(sottostringa) da cercare.
2. Scorri il testo un carattere alla volta.
3. Per ogni carattere nel testo, confrontalo con il primo carattere del pattern.
4. Se c'è una corrispondenza, controlla se anche i caratteri successivi corrispondono allo schema.
5. Se il modello è completamente abbinato, registra la posizione iniziale della corrispondenza.
6. Continua a cercare lo schema nel testo.

Esempio

Considera un testo: "ababcababcabcabc" E uno schema: "abc"

1. Inizia dalla posizione 0. Confronta "a" con il primo carattere "a" nel pattern.
2. Corrispondenza trovata, passa ai caratteri successivi: "b" con "b" e "a" con "c".
3. Continua ad abbinare: "b" con "a", "a" con "b" e "b" con "c".
4. Partita fallita in posizione 2.
5. Ricomincia dalla posizione 3. Confronta "a" con il primo carattere "a" nello schema.
6. Corrispondenza riuscita: "a" con "a", "b" con "b" e "c" con "c".
7. Registra posizione 3.

Il modello "abc" si trova nelle posizioni 0, 6 e 9.

Esempio di codice in 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;  
}  

In questo esempio, la stringSearch funzione viene utilizzata per trovare occorrenze del pattern "abc" all'interno del testo "ababcababcabcabc". Il risultato sarà un vettore contenente le posizioni di partenza delle partite.