C++ میں سٹرنگ سرچ (String Search) الگورتھم- وضاحت، مثال اور کوڈ

سٹرنگ سرچ الگورتھم کا استعمال کسی بڑے متن(سٹرنگ) کے اندر ایک مخصوص پیٹرن(سبسٹرنگ) کی موجودگی کو تلاش کرنے کے لیے کیا جاتا ہے۔ یہ الگورتھم ٹیکسٹ پروسیسنگ، تلاش اور ہیرا پھیری کے کاموں میں اہم کردار ادا کرتا ہے۔

یہ کیسے کام کرتا ہے

1. تلاش کرنے کے لیے ایک متن(سٹرنگ) اور پیٹرن(سبسٹرنگ) کے ساتھ شروع کریں۔
2. متن کے ذریعے ایک وقت میں ایک حرف کو دہرائیں۔
3. متن میں ہر ایک حرف کے لیے، پیٹرن کے پہلے حرف سے اس کا موازنہ کریں۔
4. اگر کوئی مماثلت ہے تو چیک کریں کہ آیا اس کے بعد کے حروف بھی پیٹرن سے ملتے ہیں۔
5. اگر پیٹرن مکمل طور پر مماثل ہے تو، میچ کی شروعاتی پوزیشن کو ریکارڈ کریں۔
6. متن میں پیٹرن کی تلاش جاری رکھیں۔

مثال

ایک متن پر غور کریں: "ababcababcabcabc" اور ایک نمونہ: "abc"

1. پوزیشن 0 سے شروع کریں۔ پیٹرن میں پہلے حرف "a" کے ساتھ "a" کا موازنہ کریں۔
2. میچ ملا، اگلے حروف پر جائیں: "b" کے ساتھ "b"، اور "a" کے ساتھ "c"۔
3. مماثلت جاری رکھیں: "a" کے ساتھ "b"، "a" کے ساتھ "b"، اور "c" کے ساتھ "b"۔
4. پوزیشن 2 پر میچ ناکام رہا۔
5. پوزیشن 3 سے دوبارہ شروع کریں۔ پیٹرن میں پہلے حرف "a" کے ساتھ "a" کا موازنہ کریں۔
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 فنکشن کا استعمال "ababcababcabcabc" متن کے اندر پیٹرن "abc" کی موجودگی کو تلاش کرنے کے لیے کیا جاتا ہے۔ نتیجہ ایک ویکٹر ہوگا جس میں میچوں کی ابتدائی پوزیشنیں ہوں گی۔