Competitive Programming Academy · पाठ

Polynomial String Hashing

constant time में substrings की तुलना करें

पाठ 2, कुल 4 में से13 चरण

Polynomial String Hashing, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

उपस्ट्रिंग की तेज़ तुलना

अक्सर आपको यह जाँचना पड़ता है कि दो उपस्ट्रिंग समान हैं या नहीं। अक्षर-दर-अक्षर जाँच धीमी होती है, इसलिए हम हर स्ट्रिंग को एक संख्या में बदल देते हैं। 🔢

हैश का विचार

एक हैश किसी स्ट्रिंग को एकल पूर्णांक में बदलता है। यदि दो स्ट्रिंग अलग हों, तो उनके हैश भी लगभग हमेशा अलग होते हैं।

स्ट्रिंग को बहुपद की तरह देखें

हम हर अक्षर को आधार p में एक अंक की तरह पढ़ते हैं। यह बहुपद वाला दृष्टिकोण स्ट्रिंग को एक बड़े भारित योग में बदल देता है।

h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * p

आधार और मापांक चुनें

31 जैसा अभाज्य आधार और एक बड़ा अभाज्य मापांक चुनें। मापांक संख्याओं को छोटा रखता है और ओवरफ़्लो से बचाता है।

BASE = 31
MOD = 10**9 + 9

एक हैश की गणना

स्ट्रिंग पर चलते हुए हर अक्षर को हॉर्नर के नियम से शामिल करें और हर चरण पर मापांक लें।

h = 0
for c in s:
    h = (h * BASE + ord(c)) % MOD

उपसर्ग हैश

हर स्थान के लिए एक उपसर्ग हैश संग्रहीत करें। फिर किसी भी उपस्ट्रिंग का हैश तेज़ घटाव से निकाला जा सकता है।

pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MOD

आधार की घातें

आप आधार की घातों की पहले से गणना भी करें। घटाव करते समय वे दोनों उपसर्गों को समान स्थान-माप पर लाती हैं।

pw[i] = (pw[i - 1] * BASE) % MOD

O(1) में उपस्ट्रिंग हैश

s[l..r] का हैश दो उपसर्ग हैशों का घटाव है, जिसे एक घात से मापित किया जाता है। प्रत्येक प्रश्न के लिए स्थिर समय।

def sub(l, r):
    return (pre[r] - pre[l] * pw[r - l]) % MOD

टकरावों से सावधान

दो अलग-अलग स्ट्रिंग का हैश एक जैसा हो सकता है; इसे टकराव कहते हैं। ऐसा दुर्लभ है, लेकिन प्रतियोगिताओं में कभी-कभी ऐसे इनपुट बनाए जाते हैं जो इसे उत्पन्न कर दें।

सुरक्षा के लिए दोहरा हैशिंग

दो स्वतंत्र मॉड्यूलस का उपयोग कीजिए और दोनों हैश की तुलना कीजिए। दोनों में एक साथ टकराव होना व्यावहारिक रूप से असंभव है।

हैशिंग कहाँ उपयोगी है

हैशिंग उपस्ट्रिंग तुलना, दोहराव खोजने और पैटर्न खोज को सक्षम बनाती है। यह कई काम आने वाला बहुउपयोगी औजार है।

त्वरित जाँच

कई उपस्ट्रिंग की सुरक्षित तुलना के लिए सही औजार चुनिए।

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: हैशिंग की जीत

अब आप स्ट्रिंग को बहुपद हैश में बदल सकते हैं, O(1) समय में किसी भी उपस्ट्रिंग के बारे में पूछताछ कर सकते हैं और टकरावों से बचाव कर सकते हैं। 🚀

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Polynomial String Hashing” पाठ निःशुल्क है?

हाँ—“Polynomial String Hashing” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Polynomial String Hashing” में मैं क्या सीखूँगा?

constant time में substrings की तुलना करें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।

“Polynomial String Hashing” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← Competitive Programming Academy पर वापस जाएँ