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

मान लीजिए हमारे पास एक स्ट्रिंग 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' हैं, इसलिए आउटपुट 8 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें kasai() । यह s, suff, n लेगा
• lcp :=आकार n की एक सरणी और 0 से भरें
• आमंत्रण:=आकार n की एक सरणी और 0 से भरें
• मैं के लिए 0 से n -1 की सीमा में, करो
  • आमंत्रण[suff [i]] :=i
• k :=0
• मैं के लिए 0 से n -1 की सीमा में, करो
  • यदि आमंत्रण [i] n-1 के समान है, तो
    • k :=0
    • अगले पुनरावृत्ति के लिए जाएं
  • j :=suff[inv [i] + 1]
  • जबकि i + k
  • k :=k + 1
• lcp[inv [i]] :=k
• अगर के> 0, तो
  • k :=k - 1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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]