Αλγόριθμος αναζήτησης (String Search) συμβολοσειρών σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

Ο αλγόριθμος αναζήτησης συμβολοσειρών χρησιμοποιείται για να βρει εμφανίσεις ενός συγκεκριμένου μοτίβου(υποσυμβολοσειράς) μέσα σε ένα μεγαλύτερο κείμενο(συμβολοσειρά). Αυτός ο αλγόριθμος διαδραματίζει κρίσιμο ρόλο στις εργασίες επεξεργασίας κειμένου, αναζήτησης και χειρισμού.

Πως δουλεύει

1. Ξεκινήστε με ένα κείμενο(string) και ένα μοτίβο(substring) για αναζήτηση.
2. Επαναλάβετε μέσα στο κείμενο έναν χαρακτήρα τη φορά.
3. Για κάθε χαρακτήρα του κειμένου, συγκρίνετε τον με τον πρώτο χαρακτήρα του μοτίβου.
4. Εάν υπάρχει αντιστοιχία, ελέγξτε αν οι επόμενοι χαρακτήρες ταιριάζουν επίσης με το μοτίβο.
5. Εάν το μοτίβο ταιριάζει πλήρως, καταγράψτε την αρχική θέση του αγώνα.
6. Συνεχίστε την αναζήτηση για το μοτίβο στο κείμενο.

Παράδειγμα

Σκεφτείτε ένα κείμενο: "ababcababcabcabc" Και ένα μοτίβο: "abc"

1. Ξεκινήστε από τη θέση 0. Συγκρίνετε το "a" με τον πρώτο χαρακτήρα "a" στο σχέδιο.
2. Ταίριασμα βρέθηκε, μεταβείτε στους επόμενους χαρακτήρες: "b" με "b" και "a" με "c".
3. Συνεχίστε να ταιριάζετε: "b" με "a", "a" με "b" και "b" με "c".
4. Ο αγώνας απέτυχε στη θέση 2.
5. Ξεκινήστε ξανά από τη θέση 3. Συγκρίνετε το "a" με τον πρώτο χαρακτήρα "a" στο σχέδιο.
6. Επιτυχημένη αντιστοίχιση: «α» με «α», «β» με «β» και «γ» με «γ».
7. Καταγραφή θέσης 3.

Το μοτίβο "abc" βρίσκεται στις θέσεις 0, 6 και 9.

Παράδειγμα κώδικα σε 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;  
}  

Σε αυτό το παράδειγμα, η stringSearch συνάρτηση χρησιμοποιείται για την εύρεση εμφανίσεων του μοτίβου "abc" μέσα στο κείμενο "ababcababcabcabc". Το αποτέλεσμα θα είναι ένα διάνυσμα που θα περιέχει τις αρχικές θέσεις των αγώνων.