हैशिंग

Error

अनुक्रम के केवल हैश की गणना करने के बजाय, हम इसके प्रत्येक उपसर्ग पर मान संग्रहीत कर सकते हैं। ध्यान दें कि ये संबंधित उपसर्ग के बराबर अनुक्रमों के लिए हैश मान होंगे।

इस तरह की संरचना के साथ, आप इस अनुक्रम के किसी भी उपखंड के लिए हैश मान की शीघ्रता से गणना कर सकते हैं (उपसर्ग योग के समान)।

यदि हम उपखंड [l;r] के हैश की गणना करना चाहते हैं, तो हमें उपसर्ग r पर हैश लेने की आवश्यकता है और उपसर्ग l-1 पर हैश को r-l+1 की शक्ति से p से गुणा करके घटाना होगा। ऐसा क्यों है यह स्पष्ट हो जाता है यदि आप उपसर्गों पर मान लिखते हैं और देखते हैं कि क्या होता है। मुझे उम्मीद है कि आप इस तस्वीर को देखकर सफल होंगे।



इस तरह की कार्रवाइयों के परिणामस्वरूप, हमें मूल अनुक्रम के उपखंड का हैश मिलता है। इसके अलावा, यह हैश उसके बराबर है अगर इसे इस उपखंड के बराबर अनुक्रम से हैश के रूप में माना जाता है (अन्य मूल्यों के साथ तुलना करने के लिए डिग्री या इस तरह के कोई अतिरिक्त रूपांतरण की आवश्यकता नहीं है)।

यहां दो बिंदु स्पष्ट किए जाने हैं:
1) जल्दी से p से घात r-l+1 से गुणा करने के लिए, p modulo mod की सभी संभावित शक्तियों की पूर्व गणना करना आवश्यक है।
2) यह याद रखना चाहिए कि हम सभी गणना मॉडुलो मोडुलो करते हैं, और इसलिए यह पता चल सकता है कि उपसर्ग हैश को घटाने के बाद, हमें एक ऋणात्मक संख्या मिलेगी। इससे बचने के लिए, आप घटाने से पहले हमेशा मॉड जोड़ सकते हैं। इसके अलावा, गुणा और सभी जोड़ के बाद सापेक्ष मान लेना न भूलें।

कोड में यह ऐसा दिखाई देता है:
  #शामिल <बिट्स/stdc++.h> नेमस्पेस एसटीडी का उपयोग करना; टाइपपीफ लॉन्ग लॉन्ग; कास्ट इंट मैक्सएन = 1000003; // आधार और हैश मॉड्यूल डालूँगा पी, मॉड; // उपसर्ग हैश और प्रतिपादक p एच [मैक्सएन], पॉज़ [मैक्सएन]; // उपखंड [एल; आर] के हैश की गणना ll get_segment_hash(int l, int r) { वापसी (एच [आर] + मॉड - एच [एल - 1] * पॉज़ [आर - एल + 1]% मॉड)% मॉड; } मुख्य प्रवेश बिंदु() { // किसी तरह पी और मॉड प्राप्त करें // पूर्व-गणना शक्तियां पी पाउ [0] = 1; के लिए (int i = 0; i < MAXN; i++) पॉज़ [i] = (पॉज़ [i - 1] * p)% मॉड; // // मुख्य समस्या समाधान // वापसी 0; }

अगर हमारे पास स्ट्रिंग A का हैश h_A  के बराबर है और स्ट्रिंग B का हैश h_B के बराबर है, तो हम जल्दी से स्ट्रिंग AB के हैश की गणना कर सकते हैं:
h_AB = h_A * p^|B| + h_B   <- मोडुलो सब कुछ गिन रहा है
जहां | बी | - स्ट्रिंग बी की लंबाई।

अनुक्रमों के अतिरिक्त, आप हैश सेट भी कर सकते हैं। अर्थात्, उन वस्तुओं का समुच्चय जिन पर कोई क्रम नहीं है। इसकी गणना निम्न सूत्र के अनुसार की जाती है:
हैश(ए) = \(\sum_{a \in A} p^{ord(a)}\)   <- मोडुलो सब कुछ गिन रहा है
जहां ऑर्ड एक ऐसा फ़ंक्शन है जो सेट के ऑब्जेक्ट को सभी संभावित ऑब्जेक्ट्स के बीच अपनी पूर्ण क्रमिक संख्या निर्दिष्ट करता है (उदाहरण के लिए, यदि ऑब्जेक्ट प्राकृतिक संख्याएं हैं, तो ord(x) = x, और यदि लैटिन अक्षरों को कम किया जाता है, तो ord(&& #39;a' ;) = 1, ord('b') = 2 आदि)

अर्थात्, प्रत्येक वस्तु के लिए हम इस वस्तु की संख्या की शक्ति के आधार के बराबर मूल्य को जोड़ते हैं और पूरे सेट का एक हैश प्राप्त करने के लिए इन सभी मूल्यों को जोड़ते हैं। जैसा कि सूत्र से स्पष्ट है, हैश को आसानी से पुनर्गणना किया जाता है यदि कोई तत्व सेट में जोड़ा जाता है या सेट से हटा दिया जाता है (बस आवश्यक मान जोड़ें या घटाएं)। वही तर्क,  यदि एकल तत्व जोड़े या हटाए नहीं गए हैं, लेकिन अन्य सेट (बस उनके हैश को जोड़ें / घटाएं)।

जैसा कि आप पहले से ही समझ सकते हैं, एकल तत्वों को आकार 1 के सेट के रूप में माना जाता है, जिसके लिए हम हैश की गणना कर सकते हैं। और बड़े सेट केवल ऐसे एकल सेटों का एक संघ होते हैं, जहाँ सेटों को मिलाकर, हम उनके हैश जोड़ते हैं।

वास्तव में, यह अभी भी वही बहुपद हैश है, लेकिन p^m  पर गुणांक से पहले, हमारे पास मान था संख्या n - m - 1 के अंतर्गत अनुक्रम तत्व का (जहाँ n अनुक्रम की लंबाई है), और अब यह सेट में उन तत्वों की संख्या है जिनकी पूर्ण क्रमिक संख्या m के बराबर है।

इस तरह के हैशिंग में, किसी को पर्याप्त रूप से बड़ा आधार (अधिकतम सेट आकार से बड़ा) लेना चाहिए, या ऐसी स्थितियों से बचने के लिए डबल हैशिंग का उपयोग करना चाहिए जहां पूर्ण क्रमिक संख्या एम के साथ पी ऑब्जेक्ट्स का एक सेट एक ही हैश के साथ एक ऑब्जेक्ट के साथ एक सेट के रूप में है। क्रमसूचक संख्या m+1।
 

पेड़ों को कुशलतापूर्वक हैश करने के भी कई तरीके हैं। 
इन विधियों में से एक को निम्नानुसार व्यवस्थित किया गया है:
गहराई में ट्रैवर्सल के क्रम में, हम शीर्षों को पुनरावर्ती रूप से संसाधित करते हैं। हम मानेंगे कि एकल शीर्ष का हैश p के बराबर है। बच्चों के साथ कोने के लिए, हम पहले उनके लिए एल्गोरिथम चलाते हैं, फिर बच्चों के माध्यम से हम वर्तमान सबट्री के हैश की गणना करेंगे। ऐसा करने के लिए, बच्चों के सबट्री के हैश को संख्याओं के अनुक्रम के रूप में मानें और इस क्रम से हैश की गणना करें। यह मौजूदा सबट्री का हैश होगा।
अगर चिल्ड्रन पर ऑर्डर हमारे लिए महत्वपूर्ण नहीं है, तो हैश की गणना करने से पहले, हम चाइल्ड सबट्री से हैश के क्रम को सॉर्ट करते हैं और फिर सॉर्ट किए गए क्रम से हैश की गणना करते हैं।

इस तरह आप पेड़ों के समरूपता की जांच कर सकते हैं - बस बच्चों पर बिना आदेश के हैश की गिनती करें (यानी, हर बार बच्चों के हैश को छांटते हुए)। और अगर जड़ों का हैश मेल खाता है, तो पेड़ आइसोमॉर्फिक हैं, अन्यथा नहीं।

बिना जड़ वाले वृक्षों के लिए सब कुछ एक समान तरीके से होता है, लेकिन केन्द्रक को जड़ के रूप में लिया जाना चाहिए। या दो सेंट्रोइड्स होने पर हैश की एक जोड़ी पर विचार करें।