बहुपद हैश और उनके आवेदन

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

परिचय

चलिए परिभाषा के साथ शुरू करते हैं। मान लीजिए कि हमारे पास एक स्ट्रिंग है _0..n-1 । इस रेखा का बहुपद हैश संख्या h = हैश (s। _0.n-1 ) = s ₀ + ps ₁ + p ² s ₂ + ... + p ^n-1 s _{n-1 है} , जहाँ p कुछ प्राकृतिक संख्या है (बाद में यह होगा) यह कहा गया है कि कौन सा है), और _मैं i स्ट्रिंग के i-वें चरित्र का कोड है (लगभग सभी आधुनिक भाषाओं में इसे s[i] लिखा जाता है)।

हैश की संपत्ति है कि एक ही तार की हैश जरूरी समान हैं। इसलिए, मुख्य ऑपरेशन जो हैश की अनुमति देता है, समानता के लिए दो पदार्थों की त्वरित तुलना है। बेशक, 2 लाइनों की तुलना करने के लिए, हम एक समान फ़ंक्शन लिख सकते हैं (हम मानते हैं कि लाइनों की लंबाई s और t संयोग है और n के बराबर है):

 boolean equals(char[] s, char[] t) { for (int i = 0; i < n; i++) if (s[i] != t[i]) { return false; } } return true; } 

हालांकि, सबसे खराब स्थिति में, इस फ़ंक्शन को सभी वर्णों की जांच करनी चाहिए, जो ओ (एन) के स्पर्शोन्मुख व्यवहार को देता है।

हैश के साथ तार की तुलना करें

अब देखते हैं कि हैश ऐसा कैसे करता है। चूंकि एक हैश सिर्फ एक संख्या है, हमें उनकी तुलना करने के लिए O (1) समय की आवश्यकता है। सच है, एक भोले तरीके से एक प्रतिस्थापन के हैश की गणना करने के लिए, ओ (एन) समय की आवश्यकता होती है। इसलिए, आपको गणितीय सूत्रों के साथ थोड़ा छेड़छाड़ करने की आवश्यकता है और ओ (एन) के लिए एक बार में सभी सबस्ट्रिंग के हैश को खोजने के लिए सीखना होगा। चलो _{सब्सट्रेट के एल..आर} और टी _{एक्स..वाई} (एक ही लंबाई के) की तुलना करें। हैश परिभाषा का उपयोग करते हुए, हम लिख सकते हैं:

s _L + ps _{L + 1} + ... + p ^RL-1 s _R-1 + p ^RL s _R = t _X + pt _{X + 1} + ... + p ^YX-1 t _Y-1 + p ^YX t _Y

हम बाईं ओर छोटे परिवर्तन करेंगे (दाईं ओर सब कुछ इसी तरह होगा)। हम _{सबरिंग} के हैश लिखते हैं। _0. , हमें इसकी आवश्यकता है:

हैश (s _0..R ) = s ₀ + ps ₁ + ... + p ^L-1 s _L-1 + p ^L s _L + p ^{L + 1} s _{L + 1} + ... + p ^R-1 s _R-1 + पी ^आर एस _आर

हम इस अभिव्यक्ति को दो भागों में विभाजित करेंगे ...

हैश (s _0..R ) = (s ₀ + ps ₁ + ... + p ^L-1 s _L-1 ) + (p ^L _{L L} + p ^{L + 1} s _{L + 1} + ... + p ^R-1 s _R-1 + p ^R s _R )

... और कारक ब्रैकेट को दूसरी ब्रैकेट से निकालें:

हैश (s _0..R ) = (s ₀ + ps ₁ + ... + p ^L-1 s _L-1 ) + p ^L (s _L + ps _{L + 1} + ... + p ^RL-1 s _R-1 + पी ^आरएल एस _आर )

पहले ब्रैकेट में अभिव्यक्ति कुछ भी नहीं है, जिसमें _{सब्रिंग} s _0..L-1 का हैश है, और दूसरे में, सबस्ट्रिंग s _L..R की हैश की हमें _{आवश्यकता है} । तो, हमें यह मिला:

हैश (एस। _{0. आर} ) = हैश (एस _0. ^एल _-1 ) + पी ^एल हैश ( ^{एल एल} _आर )

इसका तात्पर्य हैश के लिए निम्न सूत्र से है ( _{एल LR} ) :

हैश (s _L..R ) = (1 / p ^L ) (हैश (s _0..R ) - हैश ( _0.L-1 ))

इसी प्रकार, हमारे दूसरे विकल्प के लिए समानता हैश (t _X..Y ) = (1 / p ^X ) (हैश (t _0..Y ) - हैश (t _0..X-1 )) संतुष्ट हो जाएगी।

इन फ़ार्मुलों को ध्यान से देखने पर, हम देख सकते हैं कि किसी भी विकल्प के हैश की गणना करने के लिए, हमें इस स्ट्रिंग के उपसर्गों के केवल _0..0 , s _0..1 , ..., s _0..n-2 , s _{0 को जानने की आवश्यकता है । .n-1} । और, चूंकि प्रत्येक बाद के उपसर्ग का हैश पिछले एक के हैश के माध्यम से व्यक्त किया गया है, इसलिए उन्हें लाइन के साथ एक रेखीय मार्ग के रूप में गिनना आसान है। O (n) समय में सभी एक बार। पी की शक्तियों को भी अग्रिम में गणना की जानी चाहिए और एक सरणी में संग्रहीत किया जाना चाहिए।

कोड उदाहरण:

 //      p,     pow[0] = 1; for (int i = 1; i <= MAX; i++) { pow[i] = pow[i - 1] * p; } //     s hs[0] = s[0]; for (int i = 1; i < n; i++) { hs[i] = hs[i - 1] + pow[i] * s[i]; } //     t ht[0] = t[0]; for (int i = 1; i < m; i++) { ht[i] = ht[i - 1] + pow[i] * t[i]; } 

ऐसा लगता है कि हम अब पूरी तरह से सशस्त्र हैं और ओ (1) के लिए किसी भी सब्सट्रिंग की तुलना करने में सक्षम हैं। लेकिन सब कुछ इतना सरल नहीं है: गणितीय सूत्रों को कुछ शोधन की आवश्यकता है। उदाहरण के लिए, एक समान कोड:

 if ((hs[R] - hs[L - 1]) / pow[L] == (ht[Y] - ht[X - 1]) / pow[X]) { ... } 

काम नहीं करेगा।

• पहली टिप्पणी: एल (या एक्स ) शून्य हो सकता है, और जब hs[L - 1] गणना करते हुए, सरणी सीमाओं से परे जाएगी। हालाँकि, यदि L शून्य है, तो हमारे लिए _{अभिरुचि} s _{L..R के} हित का हैश बिल्कुल hs[R] में संग्रहित है। इसलिए, hs[L - 1] बजाय इस तरह लिखना अधिक सही है:
  

   L == 0 ? 0 : hs[L - 1] 

  ।
• दूसरी टिप्पणी: यहां तक ​​कि long प्रकार में केवल 64 बिट्स होते हैं (मैं जावा का उपयोग करता हूं), और हमारी लाइनें कई हजार लंबी हो सकती हैं, और जब हैश की गणना करते हैं, तो एक अतिप्रवाह अनिवार्य रूप से होगा। इस समस्या को हल करने का सबसे आसान तरीका है कि आप अपनी आँखें बंद कर लें। खैर, या लगभग करीब: हैश पर विचार किया जाएगा, वास्तव में, मोडुलो 2 ⁶⁴ (और इसलिए, विभाजन के शेष को लेने के संचालन करने के लिए आवश्यक नहीं होगा - सौंदर्य!)। उनकी गणना के लिए संख्या पी , सबसे पहले, लाइनों में सबसे बड़े चरित्र के कोड से अधिक होना चाहिए, और दूसरी बात, मॉड्यूल के साथ पारस्परिक रूप से सरल (हमारे मामले में, 2 ^{64 के} साथ, यानी यह विषम होना चाहिए)। ऐसा क्यों है, मैं यहां बात नहीं करूंगा - यह बीजगणित पर पुस्तकों में पाया जा सकता है। बेशक, अनिवार्य रूप से टकराव का एक मौका है, लेकिन यह बहुत छोटा है, इसलिए, जब ओलंपियाड समस्याओं को हल करते हैं, तो आप बस इसे उपेक्षित कर सकते हैं।
• तीसरी टिप्पणी: चूंकि अब हम सभी ऑपरेशन मोडुलो करते हैं, हमारे लिए विभाजन उपलब्ध नहीं है (अधिक सटीक रूप से, यह उपलब्ध है , लेकिन यह लिखना अक्षम है)। इसलिए, इससे छुटकारा पाना आवश्यक है। यह काफी सरल तरीके से किया जाता है, जिसमें स्कूल "अनुपात" कहता है: अभिव्यक्ति को एक सामान्य भाजक में घटाया जाता है, और विभाजन के बजाय गुणा का उपयोग किया जाता है:
  

   if ((hs[R] - (L == 0 ? 0 : hs[L - 1])) * pow[X] == (ht[Y] - (X == 0 ? 0 : ht[X - 1])) * pow[L]) { ... } 

अब हम उन कार्यों पर एक नज़र डालेंगे जहाँ हैश को लागू किया जा सकता है।

हैश टास्क

1. उपजाऊपन की तुलना

पहला, और सबसे महत्वपूर्ण, अनुप्रयोग, जैसा कि पहले ही उल्लेख किया गया है, दो पदार्थों की त्वरित तुलना है - हैश के साथ अन्य सभी एल्गोरिदम इसके आधार पर हैं। अंतिम अनुभाग में कोड बल्कि बोझिल है, इसलिए मैं एक अधिक सुविधाजनक कोड लिखूंगा जिसका उपयोग भविष्य में किया जाएगा।
निम्न फ़ंक्शन सबस्ट्रिंग s _L..R की गणना p ^{L से} गुणा करता है:

 long getHash(long[] h, int L, int R) { long result = h[R]; if (L > 0) result -= h[L - 1]; return result; } 

अब, हम निम्नलिखित पंक्ति के साथ दो पदार्थों की तुलना करते हैं:

 if (getHash(hs, L, R) * pow[X] == getHash(ht, X, Y) * pow[L]) { ... } 

पी की शक्तियों द्वारा गुणा को "एक शक्ति में कमी" कहा जा सकता है। पहला हैश पी ^{एल से} गुणा किया गया था, और दूसरा पी ^एक्स द्वारा इसका मतलब है कि तुलना सही होनी चाहिए, उन्हें लापता कारक से गुणा किया जाना चाहिए।
नोट: यह समझ में आता है कि अगर सबस्ट्रिंग की लंबाई मेल खाती है तो पहले चेक करें। यदि नहीं, तो सिद्धांत में लाइनें समान नहीं हो सकती हैं, और फिर आप उपरोक्त स्थिति की जांच नहीं कर सकते।

2. O (n + m) के लिए स्ट्रिंग में एक विकल्प के लिए खोजें

Hashes आप एक स्ट्रिंग में एक asymptotically कम से कम समय में एक विकल्प के लिए खोज करने के लिए अनुमति देते हैं। यह तथाकथित रबिन-कार्प एल्गोरिथ्म द्वारा किया जाता है।
चलो लंबाई n का एक स्ट्रिंग s है जिसमें हम लंबाई m के एक स्ट्रिंग t की सभी घटनाओं को खोजना चाहते हैं। स्ट्रिंग t (संपूर्ण स्ट्रिंग) के हैश और स्ट्रिंग s के सभी उपसर्गों के हैश का पता लगाएं, और फिर हम स्ट्रिंग s के साथ लंबाई m की एक विंडो के साथ आगे बढ़ेंगे, जिसमें सबस्ट्रिंग s _{i..i + m-1 की} तुलना की _{जाएगी} ।
कोड:

 //    t long ht = t[0]; for (int i = 1; i < m; i++) { ht += pow[i] * t[i]; } //    for (int i = 0; i + m <= n; i++) { if (getHash(h, i, i + m - 1) == ht * pow[i]) { //     i } } 

3. ओ में एक z- समारोह ढूँढना (एन लॉग एन)

String s का z-function अरेंज z है जिसका i- th एलिमेंट स्ट्रिंग स्ट्रिंग s में पोजिशनिंग i से शुरू होने वाले सबस्ट्रिंग के सबसे लंबे उपसर्ग के बराबर है, जो कि पूरे string s का भी उपसर्ग है। शून्य स्थिति में z- फ़ंक्शन का मान स्ट्रिंग s की लंबाई के बराबर माना जाएगा, हालांकि कुछ स्रोत इसे शून्य के लिए लेते हैं (लेकिन यह महत्वपूर्ण नहीं है)।

बेशक, ओ (एन) में जेड-फ़ंक्शन को खोजने के लिए एक एल्गोरिथ्म है । लेकिन जब आपको पता नहीं है या याद नहीं है (और एल्गोरिथ्म बोझिल है), हैश बचाव में आते हैं।

विचार इस प्रकार है: प्रत्येक i = 0, 1, ..., n-1 के लिए, हम z के लिए _एक द्विआधारी खोज _{द्वारा} खोज करेंगे, अर्थात। प्रत्येक पुनरावृत्ति पर, संभावित मूल्यों की सीमा को आधा कर दिया। यह सही है, क्योंकि समानता s _0..k-1 = s _{i..i + k-1} जरूरी सभी के लिए z _i से कम है, और यह निश्चित रूप से बड़े k के लिए नहीं है।

कोड:

 int[] z = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = n - i; //    while (left <= right) { //  middle -   int middle = (left + right) / 2; //  ,    s[0..middle-1]  s[i..i+middle-1] if (getHash(h, 0, middle - 1) * pow[i] == getHash(h, i, i + middle - 1)) { //  ,      middle,      z[i] = middle; left = middle + 1; } else { //   ,     right = middle - 1; } } } 

4. ओ (एन लॉग एन) में लेक्सोग्राफिक रूप से न्यूनतम चक्रीय लाइन ब्रेक के लिए खोजें।

एक डुवल एल्गोरिथ्म है जो हमें ओ (एन) में इस समस्या को हल करने की अनुमति देता है, लेकिन मैं कुछ काफी मजबूत ओलंपियाड प्रोग्रामर जानता हूं जिन्होंने इसका पता नहीं लगाया है। जब तक वे इसे समझते हैं, हम फिर से हैश का उपयोग करेंगे।

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

कोड:

 int bestPos = 0; for (int i = 1; i < n; i++) { int left = 1, right = n, length = 0; //  length -     while (left <= right) { int middle = (left + right) / 2; if (getHash(h, bestPos, bestPos + middle - 1) * pow[i] == getHash(h, i, i + middle - 1) * pow[bestPos]) { length = middle; left = middle + 1; } else { right = middle - 1; } } //          //      n, //       , //      if (length < n && s[i + length] < s[bestPos + length]) { bestPos = i; } } 

नोट: वास्तव में, एक तुलनित्र लूप के for लिखा जाता है जो लेक्सिकोग्राफिक रूप से दो चक्रीय पारियों की तुलना करता है। इसका उपयोग करके, सभी चक्रीय पारियों को O (n log ² n) में सॉर्ट करना संभव है।

5. ओ (एन लॉग एन) के लिए लाइन में सभी palindromes के लिए खोजें।

फिर, इस समस्या का समाधान O (n) में है । और फिर, हम इसे हैश के साथ हल करेंगे।

यदि _L = s _R , s _{L + 1} = s _R-1 इत्यादि को _{प्रतिस्थापित किया जा सकता} है, तो _{प्रतिस्थापन L L.R} को एक _ताल कहा जाता है। इसे रूसी में डालने के लिए, इसका मतलब है कि यह बाएं से दाएं, और दाएं से बाएं से उसी तरह पढ़ा जाता है।

शायद आप पहले से ही जानते हैं या अनुमान लगाते हैं कि हैश का इसके साथ क्या करना है ऐरे h[] अलावा सबस्ट्रिंग के लिए हैश युक्त _0..0 , s _0..1 , ..., s _0..n-2 , s _0..n-1 , हम दूसरे _ऐर rh[] गणना करते हैं (के लिए) "उलटा" लाइन), जिसे हम दाईं से बाईं ओर घूमेंगे। इसमें तदनुसार हैश होगा _0..n-1 , s _1..n-1 , ..., s _n-2..n-1 , s _n-1..n-1 :

 rh[n - 1] = s[n - 1]; for (int i = n - 2, j = 1; i >= 0; i--, j++) { rh[i] = rh[i + 1] + pow[j] * s[i]; } 

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

 long getRevHash(long[] rh, int L, int R) { long result = rh[L]; if (R < n - 1) result -= rh[R + 1]; return result; } boolean isPalindrome(long[] h, long[] rh, long[] pow, int L, int R) { return getHash(h, L, R) * pow[n - R - 1] == getRevHash(rh, L, R) * pow[L]; } 

अब पंक्ति में i की स्थिति पर विचार करें। आइए स्थिति i पर केंद्रित विषम लंबाई d का एक तालु (यहां तक ​​कि लंबाई के मामले में, i-1 और i के बीच केंद्रित) हो। यदि आप इसके किनारों से एक पात्र को काटते हैं, तो यह एक पैलिंड्रोम रहेगा। और इसलिए इसे तब तक जारी रखा जा सकता है जब तक कि इसकी लंबाई शून्य के बराबर न हो जाए।
इस प्रकार, यह हमारे लिए प्रत्येक स्थिति के लिए 2 मानों को संग्रहीत करने के लिए पर्याप्त है: विषम लंबाई के कितने palindromes स्थिति i में एक केंद्र के साथ मौजूद हैं, और कितने लंबाई के palindromes i-1 और i के बीच केंद्र के साथ मौजूद हैं। कृपया ध्यान दें कि ये 2 मूल्य एक दूसरे से बिल्कुल स्वतंत्र हैं, और उन्हें अलग से संसाधित करने की आवश्यकता है।

हम पहले की तरह, बाइनरी खोज लागू करते हैं:

 int[] oddCount = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = min(i + 1, n - i); while (left <= right) { int middle = (left + right) / 2; if (isPalindrome(h, rh, pow, i - middle + 1, i + middle - 1)) { oddCount[i] = middle; left = middle + 1; } else { right = middle - 1; } } } int[] evenCount = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = min(i, n - i); while (left <= right) { int middle = (left + right) / 2; if (isPalindrome(h, rh, pow, i - middle, i + middle - 1)) { evenCount[i] = middle; left = middle + 1; } else { right = middle - 1; } } } 

अब आप उदाहरण के लिए, एक पंक्ति में सभी palindromes की कुल संख्या या अधिकतम palindrome की लंबाई का पता लगा सकते हैं। स्थिति में केंद्रित अधिकतम विचित्र 2 * oddCount[i] - 1 की लंबाई को मैं 2 * oddCount[i] - 1 रूप में माना जाता है, और अधिकतम 2 * evenCount[i] ।
मुझे आपको एक बार फिर याद दिलाना है कि आपको समान और विषम लंबाई वाले पैलंड्रोमों से अधिक सावधान रहने की आवश्यकता है - एक नियम के रूप में, उन्हें एक-दूसरे से स्वतंत्र रूप से संसाधित किया जाना चाहिए।

मैट्रिक्स हैश

अंत में, हैश के अधिक परिष्कृत उपयोगों पर विचार करें। अब हमारा स्थान दो-आयामी होगा, और हम उपमात्राओं की तुलना करेंगे। सौभाग्य से, दो-आयामी मामले में हैश बहुत अच्छी तरह से सामान्यीकृत हैं (मैंने कभी भी तीन-आयामी या अधिक नहीं देखा है)।

अब संख्या p और pow सरणी के बजाय, हमारे पास दो अलग-अलग संख्याएँ p , q और दो pow1 , pow2 : प्रत्येक दिशा में एक संख्या और एक सरणी: लंबवत और क्षैतिज रूप से।

हैश में _{0..n-1, 0..m-1} को सभी i = 0, ..., n-1 , j = 0, ..., की मात्रा से m-1 कहा जाएगा। _{इ ज} ।

अब हम सीखेंगे कि ऊपरी बाएँ तत्व ₀₀ वाले उपमात्राओं के हैश की गिनती कैसे करें। जाहिर है, हैश (एक _{0..0, 0..0} ) = एक ₀₀ । यह लगभग समान रूप से स्पष्ट है कि सभी j = 1, ..., m-1 हैश (एक _{0..0, 0..j} ) = हैश (एक _{0..0, 0..j-1} ) + q के लिए ^j a _0j , सभी i = 1, ..., n-1 हैश (एक _{0..i, 0..0} ) = हैश (एक _{0..i-1, 0..0} ) + p ⁱ a के लिए _i0 । यह सीधे एक आयामी मामले से होता है।

_{सबमेट्रिक्स} के हैश की गणना कैसे करें _{0..i, 0..जे} ? कोई अनुमान लगा सकता है कि हैश (एक _{0..आई, 0..जे} ) = हैश (एक _{0..आई -1, 0..जे} ) + हैश (एक _{0. आई, 0..जे -1} ) - हैश ( _{0..i-1, 0..j-1} ) + p ⁱ q ^j a _ij । यह सूत्र निम्नलिखित बातों से प्राप्त किया जा सकता है: सभी शब्दों (हैश, मुझे याद है कि यह कई शर्तों का योग है) को जोड़ दें जो _{उपमात्राओं} के हैश को _{0..i-1, 0..j} और _{0._i, 0..j-1 बनाते हैं।} । उसी समय, हमने उन शब्दों को ध्यान में रखा जो _{सबमेट्रिक्स को 0..i-1, 0..j-1} दो बार _{बनाते हैं} , इसलिए हम उन्हें घटाते हैं ताकि उन्हें एक बार ध्यान में रखा जाए। अब, केवल एक तत्व जो p और q की संबंधित शक्तियों से गुणा किया गया है वह गायब है।

लेख के पहले भाग के रूप में लगभग समान कारणों के लिए (क्या आपने पहले ही समावेशन-बहिष्करण फार्मूले की भागीदारी पर ध्यान दिया है?), एक फ़ंक्शन एक मनमाने ढंग से _{सबमैटिक्स} के हैश की गणना करने के लिए बनाया गया है एक _{X1..x2, y1 -y2} :

 long getMatrixHash(long[][] h, int x1, int x2, int y1, int y2) { long result = h[x2][y2]; if (x1 > 0) result -= h[x1 - 1][y2]; if (y1 > 0) result -= h[x2][y1 - 1]; if (x1 > 0 && y1 > 0) result += h[x1 - 1][y1 - 1]; return result; } 

यह फ़ंक्शन submatrix के हैश को एक _{X1..x2, y1..y2} बार p ^X1 q ^y1 _{लौटाता है} ।

दो _{उपमाओं की} एक _{ax1..ax2, ay1..ay2} और एक _{bx1..bx2, by1..by2} की तुलना निम्नलिखित अभिव्यक्ति का उपयोग करके की जाती है:

 if (getMatrixHash(h, ax1, ax2, ay1, ay2) * pow1[bx1] * pow2[by1] == getMatrixHash(h, bx1, bx2, by1, by2) * pow1[ax1] * pow2[ay1]) { ... } 

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

निष्कर्ष

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