पायथन में विभिन्न क्वेरीज के लिए स्ट्रिंग के अलग-अलग सबस्ट्रिंग्स की संख्या ढूंढना

मान लीजिए हमारे पास एक स्ट्रिंग s है जिसकी लंबाई n है। हमारे पास क्वेरीज की एक लिस्ट Q भी है, जहां Q[i] में एक जोड़ा (l, r) होता है। प्रत्येक क्वेरी के लिए हमें समावेशी रेंज l और r के बीच s के अलग-अलग सबस्ट्रिंग्स की संख्या गिननी है।

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

• क्वेरी (1, 1) के लिए एकमात्र सबस्ट्रिंग 'p' है तो आउटपुट 1 है।
• क्वेरी (1, 4) के लिए सबस्ट्रिंग्स हैं 'p', 'q', 'pq', 'qp', 'pp', 'pqp', 'qpp' और 'pqpp', तो आउटपुट 8 है।
• फिर से क्वेरी (1, 1) के लिए एकमात्र सबस्ट्रिंग 'p' है तो आउटपुट 1 है।
• क्वेरी (0, 2) के लिए सबस्ट्रिंग्स हैं 'p', 'q', 'pp', 'pq', 'ppq', तो आउटपुट 5 है।

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

प्रत्येक क्वेरी के लिए, सबस्ट्रिंग निकालें, इसके सफ़िक्स ऐरे और LCP (लॉन्गेस्ट कॉमन प्रीफिक्स) ऐरे का निर्माण करें Kasai के एल्गोरिथ्म का उपयोग करके। अलग-अलग सबस्ट्रिंग्स = कुल सफ़िक्स लंबाई - LCP का योग।

• kasai(s, suff, n) फंक्शन परिभाषित करें LCP ऐरे की गणना के लिए।
• मुख्य फंक्शन में, प्रत्येक क्वेरी के लिए:
  • सबस्ट्रिंग sub = s[left:right+1] निकालें।
  • सफ़िक्स ऐरे suffix बनाएं: (इंडेक्स, सबस्ट्रिंग) जोड़े।
  • सबस्ट्रिंग द्वारा सॉर्ट करें।
  • kasai का उपयोग करके LCP की गणना करें।
  • गिनती = len(suffix[0]) + sum(len(suffix[i+1]) - lcp[i])।

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

def kasai(s, suff, n):
    lcp = [0] * n
    inv = [0] * n
    for i in range(n):
        inv[suff[i]] = i
    k = 0
    for i in range(n):
        if inv[i] == n-1:
            k = 0
            continue
        j = suff[inv[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[inv[i]] = k
        if k > 0:
            k -= 1
    return lcp

def solve(s, Q):
    res = []
    for i in range(len(Q)):
        left, right = Q[i]
        sub = s[left: right + 1]
        length = right - left + 1
        suffix = [[i, sub[i:]] for i in range(length)]
        suffix.sort(key=lambda x: x[1])
        suff, suffix = [list(t) for t in zip(*suffix)]
        lcp = kasai(sub, suff, length)
        count = len(suffix[0])
        for i in range(length-1):
            count += len(suffix[i + 1]) - lcp[i]
        res.append(count)
    return res

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

इनपुट

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

आउटपुट

[1, 8, 1, 5]