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

मान लीजिए कि हमारे पास दो तार s और क्वेरी Q का एक सेट है। जहाँ Q[i] में युग्म (l, r) है, s के l से r तक के प्रत्येक विकल्प के लिए, हमें 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" है

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

fp:=एक नई सूची
एक फ़ंक्शन को परिभाषित करें calc_fingerprint() । इसमें लगेगा
dict :=एक नया शब्दकोश, और प्रारंभ में कुंजी-मान युग्म डालें (s[0], 0)
fp:="0"
j :=1
i श्रेणी 1 से s-1 के आकार तक के लिए
- यदि s[i] dict में मौजूद नहीं है, तो
  - dict[s[i]] :=j
  - j =j+1
- fp:=fp + dict[s[i]]
fp का पूर्णांक रूप लौटाएं
मुख्य विधि से, निम्न कार्य करें -
यदि s> 10 का आकार है, तो
- i के लिए 0 से लेकर s - 10 के आकार तक, करें
  - x :=calc_fingerprint(s[index i से i+9] तक)
  - fp के अंत में x डालें
रिट:=एक नई सूची
i के लिए 0 से Q-1 के आकार के बीच में, करें
- (ए, बी):=क्यू[i]
- s1 :=इंडेक्स a-1 से b-1 में s का सबस्ट्रिंग
- k :=0
- i के लिए 0 से s के आकार के लिए - (b-a), do
  - यदि b-a> 9 और fp[a-1] fp[i] के समान नहीं है, तो
    - अगले पुनरावृत्ति के लिए जाएं
  - तानाशाही :=एक नया खाली नक्शा
  - s2 :=इंडेक्स i से i+(b-a) में s का सबस्ट्रिंग
  - मैं के लिए 0 से बी-ए की सीमा में, करते हैं
    - यदि s2[i] निर्देश में नहीं है, तो
      - यदि s1[i] dict के मूल्यों में है, तो
        
        लूप से बाहर आएं
      - dict[s2[i]] :=s1[i]
    - यदि dict[s2[i]] s1[i] के समान नहीं है, तो
      - लूप से बाहर आएं
  - अन्यथा,
    - k :=k + 1
- रिटर्न के अंत में k डालें
रिटर्न रिटर्न

उदाहरण

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

fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "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(dict[s[i]])
   return int(fp)

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]