خوارزمية البحث النصي (Text Search) في C ++- شرح ومثال ورمز

تعد خوارزمية البحث عن النص طريقة أساسية في معالجة النصوص واسترجاع المعلومات. تسمح لنا هذه الخوارزمية بتحديد وتحديد تكرارات سلسلة فرعية(أو نمط) داخل جزء أكبر من النص.

كيف تعمل

1. ابدأ بجزء أكبر من النص(أو المستند) وسلسلة فرعية للبحث عنها.
2. كرر خلال كل حرف من أحرف النص بالتسلسل.
3. قارن السلسلة الفرعية بجزء من النص له نفس طول السلسلة الفرعية. إذا تم العثور على تطابق ، قم بتسجيل الموضع الحالي.
4. انتقل إلى الموضع التالي واستمر في المقارنة.

مثال

ضع في اعتبارك النص: "دعونا نبحث عن سلسلة فرعية داخل هذا النص لنرى كيف تعمل الخوارزمية."

والسلسلة الفرعية للبحث عن: "substring"

1. ابدأ من الموضع 0. قارن Let' مع "سلسلة فرعية". لا تطابق.
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 مع "سلسلة فرعية". لا تطابق.
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 مع "سلسلة فرعية". لا تطابق.
21. الانتقال إلى الموضع 20. قارن his "مع" سلسلة فرعية. لا يوجد تطابق.
22. انتقل إلى الموضع 21. قارن is t مع "سلسلة فرعية". لا تطابق.
23. انتقل إلى الموضع 22. قارن s te  مع "سلسلة فرعية". لا تطابق.
24. انتقل إلى الموضع 23. قارن ubst  مع "سلسلة فرعية". لا تطابق.
25. انتقل إلى الموضع 24. قارن bstr مع "سلسلة فرعية". لا تطابق.
26. انتقل إلى الموضع 25. قارن stre مع "سلسلة فرعية". لا تطابق.
27. انتقل إلى الموضع 26. قارن trin  مع "سلسلة فرعية". لا تطابق.
28. انتقل إلى الموضع 27. قارن ring  مع "سلسلة فرعية". تم العثور على المباراة ، رقم قياسي 27.

تم العثور على السلسلة الفرعية "السلسلة الفرعية" في الموضع 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 يتم استخدام الوظيفة للعثور على مواضع "السلسلة الفرعية" ضمن النص. ستكون النتيجة متجهًا يحتوي على مواضع البداية للمباريات.