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

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

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

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 فنکشن کا استعمال ٹیکسٹ کے اندر سب اسٹرنگ "سبسٹرنگ" کی پوزیشن تلاش کرنے کے لیے کیا جاتا ہے۔ نتیجہ ایک ویکٹر ہوگا جس میں میچوں کی ابتدائی پوزیشنیں ہوں گی۔