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

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

كيف تعمل

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

مثال

النظر في نص: "ababcabcabcabc" ونمط: "abc"

1. ابدأ من الموضع 0. قارن "أ" بالحرف الأول "أ" في النمط.
2. تم العثور على تطابق ، انتقل إلى الأحرف التالية: "ب" مع "ب" ، و "أ" مع "ج".
3. استمر في المطابقة: "b" مع "a" ، و "a" مع "b" ، و "b" مع "c".
4. فشلت المباراة في الموضع 2.
5. ابدأ مرة أخرى في الموضع 3. قارن "أ" بالحرف الأول "أ" في النمط.
6. مطابقة ناجحة: "a" مع "a" و "b" مع "b" و "c" مع "c".
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" داخل النص "ababcabcabcabc". ستكون النتيجة متجهًا يحتوي على مواضع البداية للمباريات.