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