C++ में सबस्ट्रिंग खोज: सरलता से प्रदर्शन तक

प्रस्तावना: क्यों "बस find()" हमेशा जवाब नहीं है

एक स्थिति की कल्पना करें: आप एक लॉग पार्सर लिख रहे हैं जो प्रति सेकंड लाखों पंक्तियों को संसाधित करता है, या एक टेक्स्ट सर्च इंजन। सबसे पहले जो विचार आता है वह है std::string::find() को कॉल करना। "काम करता है? काम करता है। और क्या चाहिए?" - 90% प्रोग्रामर ऐसा सोचते हैं। और वे सही हैं... जब तक वह क्षण नहीं आता जब 10 मिलीसेकंड पूरे एप्लिकेशन का भाग्य तय करते हैं।

Stack Overflow पर "Check if a string contains a string in C++" प्रश्न ने सैकड़ों हज़ारों व्यूज़ एकत्र किए हैं। और यह कोई संयोग नहीं है। यह प्रतीत होने वाला सरल कार्य कई छिपे हुए खतरों को समेटे हुए है: सर्च एल्गोरिदम के चयन से लेकर C++17 और C++20 की आधुनिक क्षमताओं के सही उपयोग तक।

इस लेख में, हम केवल यह नहीं दिखाएंगे कि कैसे जाँच करें कि स्ट्रिंग में सबस्ट्रिंग है या नहीं। हम ऐसा करने के 7 तरीकों का विश्लेषण करेंगे, वास्तविक डेटा पर उनके प्रदर्शन की तुलना करेंगे, और विभिन्न परिदृश्यों के लिए स्पष्ट सिफारिशें देंगे। चलिए शुरू करते हैं!

क्लासिक तरीका: std::string::find()

आधार से शुरू करते हैं, जो हर कोई जानता है। find() विधि सबस्ट्रिंग के पहले प्रकट होने की स्थिति लौटाती है या यदि कुछ नहीं मिलता है तो विशेष मान std::string::npos लौटाती है।

#include <iostream>\n#include <string>\n\nint main() {\n    std::string haystack = "Hello, C++ developer!";\n    std::string needle = "C++";\n    \n    if (haystack.find(needle) != std::string::npos) {\n        std::cout << "सबस्ट्रिंग मिल गई!" << std::endl;\n    }\n    \n    // प्रारंभिक स्थिति निर्दिष्ट करके खोज\n    size_t pos = haystack.find("C++", 5); // 5वें अक्षर से शुरू करें\n    return 0;\n}

लाभ: सरलता, पठनीयता, STL में निर्मित।
\nनुकसान: यह नेव (भोला) सर्च एल्गोरिदम का उपयोग करता है (सबसे खराब स्थिति में O(n*m))। छोटी स्ट्रिंग्स के लिए आदर्श, लंबी स्ट्रिंग्स के लिए धीमा हो सकता है।

find() कब बुरा है?

यदि आप 10⁵+ वर्णों वाली स्ट्रिंग में सबस्ट्रिंग खोज रहे हैं, और सबस्ट्रिंग लंबी और दोहराई जाने वाली है (जैसे, "aaaaaaaaaaaaaaaaaaaaab" में "aaaaaab"), तो नेव एल्गोरिदम खराब होने लगता है। ऐसे मामलों में, find() अनुकूलित विकल्पों की तुलना में 10-100 गुना धीमा काम कर सकता है।

string_view: हल्कापन और गति

C++17 के आगमन के साथ, हमारे पास std::string_view आया - स्ट्रिंग का एक गैर-स्वामित्व वाला प्रतिनिधित्व। यह उन फ़ंक्शनों के लिए आदर्श है जो केवल डेटा पढ़ते हैं, उसे कॉपी किए बिना।

#include <iostream>\n#include <string_view>\n\nbool contains(std::string_view haystack, std::string_view needle) {\n    return haystack.find(needle) != std::string_view::npos;\n}\n\nint main() {\n    std::string_view text = "C++ में अनुकूलन एक कला है";\n    std::string_view pattern = "कला";\n    \n    if (contains(text, pattern)) {\n        std::cout << "मिल गया!" << std::endl;\n    }\n    return 0;\n}

यह तेज़ क्यों है? std::string को फ़ंक्शन में पास करते समय कॉपी होती है (यदि संदर्भ द्वारा पास नहीं किया जाता है)। string_view बस पॉइंटर और लंबाई कॉपी करता है - कोई आवंटन नहीं। बार-बार उपस्थिति जाँच कॉल के लिए, यह प्रदर्शन में 30-40% तक का लाभ देता है।

एल्गोरिदमिक अपग्रेड: Boyer-Moore और KMP

यदि आप वास्तव में बड़े डेटा के साथ काम कर रहे हैं, तो सबस्ट्रिंग खोज के क्लासिक एल्गोरिदम को याद करने का समय आ गया है। C++17 में STL से सर्च एल्गोरिदम आए:

\n
• std::boyer_moore_searcher - लंबे पैटर्न के लिए सबसे तेज़ में से एक
\n
• std::boyer_moore_horspool_searcher - सरलीकृत संस्करण, छोटे पैटर्न पर तेज़
\n
• std::default_searcher - नेव खोज पर एक रैपर
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "C++ में खोज एल्गोरिदम बहुत तेज़ हो सकते हैं";\n