स्ट्रिंग हैशिंग

स्ट्रिंग हैशिंग के बहुत सारे तरीके मौजूद हैं, लेकिन इस कोर्स में हम एक ऐसे आम और सहज तरीके पर चर्चा करेंगे, जिसे लागू करना काफी आसान है। यह तरीका प्रतिस्पर्धी प्रोग्रामिंग प्रतियोगिताओं और एल्गोरिथमिक इंटरव्यूज़ में व्यापक रूप से इस्तेमाल होता है।

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, जिसके अक्षर हैं। हम ऐसा एक साधन चाहते हैं जिससे हम किसी भी लगातार आने वाली उपस्ट्रिंग का हैश सरलता से निकाल सकें।

एक मजबूत हैश फ़ंक्शन चुनना

एक उदाहरण ऐसे मजबूत हैश फ़ंक्शन का, जो व्यावहारिक तौर पर ठीक से काम करता है, वह है—a function जो स्ट्रिंग में मौजूद हर कैरेक्टर के न्यूमेरिक वैल्यू को किसी अभाज्य संख्या p की पावर से गुणा करता है और फिर इसे m से मॉड लेता है:

यहाँ p और m दोनों अभाज्य संख्याएँ हैं। p के लिए आप 1997, 127 इत्यादि का उपयोग कर सकते हैं। m जितना बड़ा होगा, टकराव (collision) की संभावना उतनी कम रहेगी, लेकिन बहुत बड़ा m चुनने से कंप्यूटेशन की गति धीमी पड़ सकती है। इसलिए कई जगहों पर m को या रखा जाता है। यह कुछ इस तरह से लागू किया जा सकता है:

s = input()                                  # उपयोगकर्ता इनपुट (मनचाही लंबाई में)
p = 1997                                     # p: एक अभाज्य संख्या
m = 1_000_000_007                            # m: एक काफ़ी बड़ा अभाज्य

h = [0] * (len(s) + 1)                       # h को 0 से इनिशियलाइज़ करें
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # वर्तमान वर्ण को जोड़ें
    h[i + 1] *= p                            # p की सभी शक्तियों को 1 से गुना दें
    h[i + 1] %= m                            # हर इटररेशन पर m से मॉड लो

यहाँ हम हर इंडेक्स के लिए रोलिंग हैश फ़ंक्शन निकाल रहे हैं (जो कुछ हद तक एक प्रीफ़िक्स सम एरे जैसा दिखता है):

ध्यान दें कि इस कार्यान्वयन में h की पहली एंट्री एक डमी वेरिएबल है, जिसका मान 0 होता है। साथ ही, हम देख सकते हैं कि प्रत्येक h का मान पिछले h पर आधारित है:

स्ट्रिंग के किसी भी सबस्ट्रिंग का हैश निकालना

मान लीजिए हमें दो उपस्ट्रिंग्स s[l1; r1) और s[l2; r2) (जो एक ही लंबाई की हैं) की तुलना करके उनकी समानता जाँचनी है। हम चाहते हैं कि उन दोनों सबस्ट्रिंग्स का एक सामान्यीकृत हैश (normalized hash) निकालें, और अगर ये दोनों हैश एक जैसे आएँ, तो हम कहेंगे कि सबस्ट्रिंग्स बराबर हैं।

अब हमारे पास हैश फ़ंक्शन h है, तो किसी भी सबस्ट्रिंग का हैश निकालना संभव है। लेकिन यह उतना सरल नहीं है जितना सीधे राइट इंडेक्स से लेफ़्ट इंडेक्स को घटा देने में लगता है।

मान लीजिए हमारे पास लेफ़्ट इंडेक्स l और राइट इंडेक्स r है, और हमें s[l; r) का हैश चाहिए। आदर्श रूप से हम वह हैश चाहते हैं जो हमें तभी मिलता, जब हम substring s[l; r) पर उसी तरह से शुरुआत से हैश बनाते। क्योंकि हमने स्ट्रिंग के हर कैरेक्टर को अभाज्य संख्या p की पावर से गुणा करके जमा किया था, इसलिए हमें हैश से लेफ़्ट हिस्से को एडजस्ट करना होगा, ताकि पावर सही ढंग से कैलिब्रेट हो सके:

यही वही मान होगा जिसे हम s[l; r) के लिए शुरुआत से हैश करते हुए प्राप्त करते (मानो s[l; r) खुद ही एक नई स्ट्रिंग हो)। ध्यान दें कि यहाँ पहला कैरेक्टर p^{r-l} की पावर से गुणा हो रहा है, जो उस सबस्ट्रिंग की लंबाई को दर्शाता है, जबकि आख़िरी कैरेक्टर p^1 से गुणा हो रहा है, ठीक उसी तरह जैसे हम पूरी स्ट्रिंग का हैश निकालते वक्त आख़िरी अक्षर पर करते हैं।

इससे सुनिश्चित हो जाता है कि जब हम अलग-अलग इंटरवल [1; 5) और [4; 8) इत्यादि का हैश निकालेंगे, तो भले ही पावर अलग-अलग हों, पर अगर कैरेक्टर्स वही हैं, तो हैश एक ही आए। यह काम h[l] को (r-l) के अंतर से स्केल करके किया जाता है:

# पावर को पहले से ही प्रीकम्प्यूट कर लें
pows = [1] * (len(s) + 1)                  # सभी पावर को पहले से संग्रहित करें
for i in range(len(s)):                    # 1...n तक की सभी पावर
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # हर इटररेशन में m से मॉड लें

# [l; r) का हैश O(1) में निकालें
res = h[r] - h[l] * pows[r - l]            # h[l] को (r-l) के अंतर से स्केल करें
res %= m                                   # परिणाम को m से मॉड लें
print(res)

यदि इनपुट स्ट्रिंग s के रूप में hello hellyo दिया गया हो, तो h और pows की यह वैल्यूज़ बनेंगी, और कुछ क्वेरी चलाने पर हमें निम्नलिखित परिणाम मिलेंगे:

# s ->     h       e          l          l          o                     h          e          l          l          y          o
h    = [0, 207688, 414954633, 664611981, 230332444, 974109122, 295966923, 46148782,  159318707, 159671329, 863857463, 123583173, 795816426]
pows = [1, 1997,   3988009,   964053924, 215672753, 698484731, 873998049, 374091638, 60995857,  808725582, 24975949,  876969810, 308698313]
# i ->  0  1       2          3          4          5          6          7          8          9          10         11         12

# hash for s[0: 3] (hel)    -> 664611981  (l = 0, r = 3)
# hash for s[6: 9] (hel)    -> 664611981  (l = 6, r = 9)
# hash for s[0: 5] (hello)  -> 974109122  (l = 0, r = 5)
# hash for s[6: 11] (helly) -> 974129092  (l = 6, r = 11)

तो, क्या आप किसी स्ट्रिंग को हैश करने और फिर उससे संबन्धित क्वेरीज़ का जवाब देने के लिए तैयार हैं? अब आप जान गए हैं कि किसी भी सबस्ट्रिंग का हैश कैसे निकाला जा सकता है।

इनपुट

इनपुट की पहली पंक्ति में स्ट्रिंग s होगी (1 ≤ |s| ≤ )।

दूसरी पंक्ति में एक इंटीजर q (1 ≤ q ≤ 100000) दिया होगा, जो क्वेरीज़ की संख्या दर्शाता है।

अगली q पंक्तियों में इंडेक्स के जोड़े (0 ≤ ≤ |s|) दिए होंगे।

आउटपुट

प्रोग्राम को हर क्वेरी के लिए [l_i; r_i) इंटरवल का हैश प्रिंट करना चाहिए।

उदाहरण