सांस्कृतिक संपर्क
अनुक्रमों के अतिरिक्त, आप हैश सेट भी कर सकते हैं। अर्थात्, उन वस्तुओं का समुच्चय जिन पर कोई क्रम नहीं है। इसकी गणना निम्न सूत्र के अनुसार की जाती है:
हैश(ए) = \(\sum_{a \in A} p^{ord(a)}\) <- मोडुलो सब कुछ गिन रहा है
जहां ऑर्ड एक ऐसा फ़ंक्शन है जो सेट के ऑब्जेक्ट को सभी संभावित ऑब्जेक्ट्स के बीच अपनी पूर्ण क्रमिक संख्या निर्दिष्ट करता है (उदाहरण के लिए, यदि ऑब्जेक्ट प्राकृतिक संख्याएं हैं, तो ord(x) = x, और यदि लैटिन अक्षरों को कम किया जाता है, तो ord(&& #39;a' ;) = 1, ord('b') = 2 आदि)
अर्थात्, प्रत्येक वस्तु के लिए हम इस वस्तु की संख्या की शक्ति के आधार के बराबर मूल्य को जोड़ते हैं और पूरे सेट का एक हैश प्राप्त करने के लिए इन सभी मूल्यों को जोड़ते हैं। जैसा कि सूत्र से स्पष्ट है, हैश को आसानी से पुनर्गणना किया जाता है यदि कोई तत्व सेट में जोड़ा जाता है या सेट से हटा दिया जाता है (बस आवश्यक मान जोड़ें या घटाएं)। वही तर्क, यदि एकल तत्व जोड़े या हटाए नहीं गए हैं, लेकिन अन्य सेट (बस उनके हैश को जोड़ें / घटाएं)।
जैसा कि आप पहले से ही समझ सकते हैं, एकल तत्वों को आकार 1 के सेट के रूप में माना जाता है, जिसके लिए हम हैश की गणना कर सकते हैं। और बड़े सेट केवल ऐसे एकल सेटों का एक संघ होते हैं, जहाँ सेटों को मिलाकर, हम उनके हैश जोड़ते हैं।
वास्तव में, यह अभी भी वही बहुपद हैश है, लेकिन pm पर गुणांक से पहले, हमारे पास मान था संख्या n - m - 1 के अंतर्गत अनुक्रम तत्व का (जहाँ n अनुक्रम की लंबाई है), और अब यह सेट में उन तत्वों की संख्या है जिनकी पूर्ण क्रमिक संख्या m के बराबर है।
इस तरह के हैशिंग में, किसी को पर्याप्त रूप से बड़ा आधार (अधिकतम सेट आकार से बड़ा) लेना चाहिए, या ऐसी स्थितियों से बचने के लिए डबल हैशिंग का उपयोग करना चाहिए जहां पूर्ण क्रमिक संख्या एम के साथ पी ऑब्जेक्ट्स का एक सेट एक ही हैश के साथ एक ऑब्जेक्ट के साथ एक सेट के रूप में है। क्रमसूचक संख्या m+1।
Problem
18वीं शताब्दी की शुरुआत में, यूरोपीय खोजकर्ताओं का एक समूह जनजातियों के एक समूह द्वारा बसाए गए एक द्वीप पर पहुंचा, जो कभी भी यूरोपीय सभ्यता के प्रतिनिधियों के संपर्क में नहीं आया था।
मूल निवासियों के साथ सफलतापूर्वक संपर्क स्थापित करने के लिए, समूह का नेता प्रत्येक जनजाति के नेता को उपहार देने की योजना बनाता है। इसके लिए, वह कीमती पत्थरों के समान कांच की एक लंबी श्रृंखला लाया।
आइए स्ट्रिंग को एक स्ट्रिंग एस के रूप में दर्शाते हैं, जिसमें अंग्रेजी वर्णमाला के छोटे अक्षर शामिल हैं, जहां प्रत्येक अक्षर का अर्थ संबंधित स्थिति में कांच के टुकड़े का प्रकार है।
शोधकर्ता श्रृंखला को कुछ टुकड़ों में काटने जा रहे हैं, और फिर समूह द्वारा सामना किए गए प्रत्येक जनजाति के नेता को ठीक एक टुकड़ा सौंप देंगे। अनुसंधान नेता ने श्रृंखला को निम्नलिखित नियमों के अनुसार टुकड़ों में विभाजित करने का निर्णय लिया:
<उल>
काटने में ज्यादा समय खर्च न करने के लिए, प्रत्येक टुकड़े को श्रृंखला में कांच के आसन्न टुकड़ों का एक समूह होना चाहिए, जो कि स्ट्रिंग एस का एक सबस्ट्रिंग है।
कांच के सभी टुकड़ों का उपयोग किया जाना चाहिए, अर्थात, कांच के प्रत्येक टुकड़े को ठीक एक टुकड़े में शामिल किया जाना चाहिए।
चूंकि शोधकर्ता नहीं जानते कि आदिवासी कुछ प्रकार के कांच को कैसे महत्व देंगे, वे चाहते हैं कि प्रत्येक प्रमुख को आदेश की परवाह किए बिना कांच का एक ही सेट मिले। दूसरे शब्दों में, किसी भी प्रकार के कांच के लिए, प्रत्येक टुकड़े में इस प्रकार के कांच की संख्या समान होनी चाहिए।
शोधकर्ताओं को यह नहीं पता है कि द्वीप पर कितनी जनजातियां रहती हैं, इसलिए तैयार किए गए टुकड़ों की संख्या यथासंभव बड़ी होनी चाहिए।
प्राप्त किए जा सकने वाले टुकड़ों की अधिकतम संख्या निर्धारित करने में प्रबंधक की सहायता करें।
इनपुट:
पहली पंक्ति में स्ट्रिंग s (1 <= |s| <= 5000000) है।
आउटपुट:
एकल संख्या प्रिंट करें - टुकड़ों की अधिकतम संभावित संख्या जिसमें शोधकर्ता समूह के नेता द्वारा तैयार की गई किसी भी शर्त का उल्लंघन किए बिना श्रृंखला को काट सकते हैं।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
| अब्बाबबब |
3 |
| आबब |
1 |
स्पष्टीकरण:
पहले उदाहरण में, शोधकर्ता श्रृंखला 'अब्बाब्बब' को तोड़ सकते हैं; टुकड़े 'एबीबी', 'एबीबी', 'बाब', तो वे मिलने वाले प्रत्येक जनजाति के नेता को 'ए' प्रकार का एक गिलास मिलेगा; और 'b'.
के दो टुकड़े
दूसरे उदाहरण में, सभी शर्तों को ध्यान में रखते हुए स्ट्रिंग को श्रृंखला के एक से अधिक टुकड़ों में विभाजित नहीं किया जा सकता है।