राबिन-कार्प एल्गोरिथम क्या है?

राबिन-कार्प एल्गोरिदम एक स्ट्रिंग पैटर्न मिलान एल्गोरिदम है जो एक बड़े पाठ के भीतर एक पैटर्न की घटनाओं को कुशलतापूर्वक खोजता है। इसे 1987 में माइकल ओ. राबिन और रिचर्ड एम. कार्प द्वारा विकसित किया गया था।

एल्गोरिदम पाठ के पैटर्न और सबस्ट्रिंग के हैश मानों की तुलना करने के लिए हैशिंग तकनीक का उपयोग करता है। यह इस प्रकार काम करता है:

• पैटर्न के हैश मान और पाठ की पहली विंडो की गणना करें।

• पाठ पर पैटर्न को एक समय में एक स्थिति में स्लाइड करें और हैश मानों की तुलना करें।

• यदि हैश मान मेल खाते हैं, तो मिलान की पुष्टि करने के लिए पैटर्न के वर्णों और पाठ की वर्तमान विंडो की तुलना करें।

• यदि कोई मिलान है, तो मिलान की स्थिति/सूचकांक रिकॉर्ड करें।

• रोलिंग हैश फ़ंक्शन का उपयोग करके टेक्स्ट की अगली विंडो के लिए हैश मान की गणना करें।

• पाठ की सभी स्थितियों की जांच होने तक चरण 3 से 5 दोहराएं।

रोलिंग हैश फ़ंक्शन पिछली विंडो में पहले वर्ण के योगदान को घटाकर और नई विंडो में अगले वर्ण के योगदान को जोड़कर प्रत्येक नई विंडो के लिए हैश मान को कुशलतापूर्वक अपडेट करता है। यह प्रत्येक विंडो के लिए स्क्रैच से हैश मान की पुनर्गणना से बचने में मदद करता है, जिससे एल्गोरिदम अधिक कुशल हो जाता है।

पैटर्न खोज के लिए राबिन-कार्प एल्गोरिदम के लिए PHP प्रोग्राम

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

आउटपुट

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

कोड की व्याख्या

PHP कोड पैटर्न खोज के लिए राबिन-कार्प एल्गोरिदम लागू करता है। यह इनपुट के रूप में एक पैटर्न और एक टेक्स्ट लेता है और टेक्स्ट के भीतर पैटर्न की घटनाओं की खोज करता है। एल्गोरिथ्म पैटर्न और पाठ की पहली विंडो के लिए हैश मानों की गणना करता है। इसके बाद यह वर्तमान विंडो के हैश मान और पैटर्न की तुलना करते हुए पैटर्न को टेक्स्ट पर स्लाइड करता है। यदि हैश मान मेल खाते हैं, तो यह वर्णों को एक-एक करके सत्यापित करता है। यदि कोई मिलान पाया जाता है, तो यह उस सूचकांक को प्रिंट करता है जहां पैटर्न पाया जाता है। एल्गोरिदम प्रत्येक विंडो के लिए हैश मान को कुशलतापूर्वक अपडेट करने के लिए रोलिंग हैश फ़ंक्शन का उपयोग करता है। कोड "ABCABCABCABC" पाठ में "BC" पैटर्न की खोज करके एल्गोरिदम के उपयोग को प्रदर्शित करता है।

निष्कर्ष

निष्कर्ष में, PHP प्रोग्राम पैटर्न खोज के लिए राबिन-कार्प एल्गोरिदम को प्रभावी ढंग से कार्यान्वित करता है। रोलिंग हैश फ़ंक्शन का उपयोग करके और हैश मानों की तुलना करके, एल्गोरिदम कुशलतापूर्वक एक बड़े पाठ के भीतर एक पैटर्न की घटनाओं की खोज करता है। प्रोग्राम उन सूचकांकों की सही पहचान करता है जहां पैटर्न पाठ में पाया जाता है और परिणाम आउटपुट करता है। एक स्पष्ट संरचना और उचित हैश गणना के साथ, प्रोग्राम PHP में पैटर्न खोज के लिए राबिन-कार्प एल्गोरिदम की कार्यक्षमता और उपयोगिता प्रदर्शित करता है।