पायथन में प्रत्येक क्वेरी के लिए समान सबस्ट्रिंग्स की संख्या गिनना

मान लीजिए हमारे पास दो स्ट्रिंग्स s और क्वेरी का सेट Q है। जहां Q[i] में जोड़ा (l, r) होता है, s के l से r तक के प्रत्येक सबस्ट्रिंग के लिए, हमें s के x से y तक के सबस्ट्रिंग्स की संख्या ढूंढनी है जहां वे समान हैं। दो स्ट्रिंग्स s और t समान हैं यदि वे इन नियमों का पालन करते हैं:

• वे समान लंबाई के हैं
• प्रत्येक इंडेक्स जोड़ी (i, j) के लिए, यदि s[i] == s[j], तो t[i] = t[j] संतुष्ट होना चाहिए, और इसी तरह यदि s[i] != s[j], तो t[i] और t[j] अलग होने चाहिए।

उदाहरण के लिए, यदि इनपुट है s = "hjhhbcbk", Q = [(1,2), (2,4)], तो आउटपुट होगा [6, 1] क्योंकि:

• पहली क्वेरी के लिए समान सबस्ट्रिंग्स हैं "hj", "jh", "hb", "bc", "cb" और "bk"।
• दूसरी क्वेरी के लिए समान सबस्ट्रिंग "jhh" है।

समाधान दृष्टिकोण

स्ट्रक्चरल समतुल्यता के लिए फिंगरप्रिंटिंग (आइसोमॉर्फिक स्ट्रिंग्स) का उपयोग करें। लंबाई > 10 के लिए फिंगरप्रिंट प्रीकंप्यूट करें। प्रत्येक क्वेरी सबस्ट्रिंग के लिए, सभी समान लंबाई के सबस्ट्रिंग्स के खिलाफ फिंगरप्रिंट और कैरेक्टर मैपिंग का उपयोग करके मिलान जांचें।

• calc_fingerprint(s): कैरेक्टर के पहले घटना इंडेक्स के आधार पर पैटर्न स्ट्रिंग बनाएं।
• लंबाई > 10 के लिए सभी विंडो के फिंगरप्रिंट प्रीकंप्यूट करें।
• प्रत्येक क्वेरी (a, b) के लिए:
  • पैटर्न s1 निकालें।
  • सभी संभावित सबस्ट्रिंग्स s2 पर पुनरावृति करें।
  • लंबाई > 10 के लिए फिंगरप्रिंट का उपयोग करके शीघ्र अस्वीकृति करें।
  • कैरेक्टर मैपिंग dict का उपयोग करके आइसोमॉर्फिज्म सत्यापित करें।
  • मिलान गिनें।

पायथन कार्यान्वयन

fp = []

def calc_fingerprint(s):
    dict = {s[0]: 0}
    fp_str = "0"
    j = 1
    for i in range(1, len(s)):
        if s[i] not in dict:
            dict[s[i]], j = j, j+1
        fp_str += str(dict[s[i]])
    return int(fp_str)

def solve(s, Q):
    if len(s) > 10:
        for i in range(0, len(s)-10):
            fp.append(calc_fingerprint(s[i: i+10]))
    ret = []
    for i in range(len(Q)):
        a, b = Q[i]
        s1 = s[a-1:b]
        k = 0
        for i in range(len(s)-(b-a)):
            if b-a > 9 and fp[a-1] != fp[i]:
                continue
            dict = {}
            s2 = s[i:i+(b-a)+1]
            for i in range(b-a+1):
                if s2[i] not in dict:
                    if s1[i] in dict.values():
                        break
                    dict[s2[i]] = s1[i]
                if dict[s2[i]] != s1[i]:
                    break
            else:
                k += 1
        ret.append(k)
    return ret

s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))

इनपुट

"hjhhbcbk", [(1,2), (2,4)]

आउटपुट

[6, 1]