close

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

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

Πως δουλεύει

  1. Ξεκινήστε με ένα μεγαλύτερο κομμάτι κειμένου(ή έγγραφο) και μια δευτερεύουσα συμβολοσειρά για αναζήτηση.
  2. Επαναλάβετε σε κάθε χαρακτήρα του κειμένου διαδοχικά.
  3. Συγκρίνετε τη δευτερεύουσα συμβολοσειρά με ένα τμήμα του κειμένου που έχει το ίδιο μήκος με τη δευτερεύουσα συμβολοσειρά. Εάν βρεθεί αντιστοιχία, καταγράψτε την τρέχουσα θέση.
  4. Μεταβείτε στην επόμενη θέση και συνεχίστε τη σύγκριση.

Παράδειγμα

Σκεφτείτε το κείμενο: "Ας αναζητήσουμε μια υποσυμβολοσειρά σε αυτό το κείμενο για να δούμε πώς λειτουργεί ο αλγόριθμος."

Και η υποσυμβολοσειρά για αναζήτηση: "substring"

  1. Ξεκινήστε από τη θέση 0. Συγκρίνετε Let' με "substring". Δεν ταιριάζει.
  2. Μετακίνηση στη θέση 1. Συγκρίνετε et's με "υποσυμβολοσειρά". Δεν ταιριάζει.
  3. Μετακίνηση στη θέση 2. Σύγκριση t's " με "υποσυμβολοσειρά". Δεν ταιριάζει.
  4. Μετακίνηση στη θέση 3. Συγκρίνετε 's s με "υποσυμβολοσειρά". Δεν ταιριάζει.
  5. Μετακίνηση στη θέση 4. Συγκρίνετε se με "υποσυμβολοσειρά". Δεν ταιριάζει.
  6. Μετακίνηση στη θέση 5. Σύγκριση sea με "υποσυμβολοσειρά". Δεν ταιριάζει.
  7. Μετακίνηση στη θέση 6. Σύγκριση earc με "υποσυμβολοσειρά". Δεν ταιριάζει.
  8. Μετακίνηση στη θέση 7. Συγκρίνετε arch με "υποσυμβολοσειρά". Δεν ταιριάζει.
  9. Μετακίνηση στη θέση 8. Σύγκριση rch " με "υποσυμβολοσειρά". Δεν ταιριάζει.
  10. Μετακίνηση στη θέση 9. Σύγκριση ch w με "υποσυμβολοσειρά". Δεν ταιριάζει.
  11. Μετακινηθείτε στη θέση 10. Συγκρίνετε h wi με το "substring". Δεν ταιριάζει.
  12. Μετακίνηση στη θέση 11. Σύγκριση " wit με "υποσυμβολοσειρά". Δεν ταιριάζει.
  13. Μετακίνηση στη θέση 12. Συγκρίνετε with με "υποσυμβολοσειρά". Δεν ταιριάζει.
  14. Μετακίνηση στη θέση 13. Σύγκριση ithi με "υποσυμβολοσειρά". Δεν ταιριάζει.
  15. Μετακίνηση στη θέση 14. Σύγκριση thin με "υποσυμβολοσειρά". Δεν ταιριάζει.
  16. Μετακίνηση στη θέση 15. Σύγκριση hinn με "υποσυμβολοσειρά". Δεν ταιριάζει.
  17. Μετακίνηση στη θέση 16. Συγκρίνετε in t με "υποσυμβολοσειρά". Δεν ταιριάζει.
  18. Μετακίνηση στη θέση 17. Σύγκριση n th με "υποσυμβολοσειρά". Δεν ταιριάζει.
  19. Μετακίνηση στη θέση 18. Σύγκριση " thi με "υποσυμβολοσειρά". Δεν ταιριάζει.
  20. Μετακίνηση στη θέση 19. Σύγκριση this με "substring". Δεν ταιριάζει.
  21. Μετακίνηση στη θέση 20. Σύγκριση his " με "υποσυμβολοσειρά". Δεν ταιριάζει.
  22. Μετακίνηση στη θέση 21. Σύγκριση is t με "υποσυμβολοσειρά". Δεν ταιριάζει.
  23. Μετακίνηση στη θέση 22. Σύγκριση s te  με "substring". Δεν ταιριάζει.
  24. Μετακίνηση στη θέση 23. Σύγκριση ubst  με "substring". Δεν ταιριάζει.
  25. Μετακίνηση στη θέση 24. Σύγκριση bstr με "substring". Δεν ταιριάζει.
  26. Μετακίνηση στη θέση 25. Σύγκριση stre με "υποσυμβολοσειρά". Δεν ταιριάζει.
  27. Μετακίνηση στη θέση 26. Σύγκριση trin  με "υποσυμβολοσειρά". Δεν ταιριάζει.
  28. Μετακίνηση στη θέση 27. Σύγκριση ring  με "υποσυμβολοσειρά". Βρέθηκε ταίριασμα, θέση ρεκόρ 27.

Η υποσυμβολοσειρά "substring" βρίσκεται στη θέση 27 μέσα στο κείμενο.

Παράδειγμα κώδικα σε C++ 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

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