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

मान लीजिए हमें दो तार दिए गए हैं, दोनों लोअरकेस अक्षरों से बने हैं। हमें दी गई शर्तों को पूरा करने वाले चौगुनी (p, q, r, s) की संख्या ज्ञात करनी है -

0 <=p <=q <=पहली स्ट्रिंग की लंबाई।
0 <=r <=s <=दूसरी स्ट्रिंग की लंबाई।
पहली स्ट्रिंग के इंडेक्स पी से शुरू होने वाली और पहली स्ट्रिंग के इंडेक्स क्यू पर समाप्त होने वाली सबस्ट्रिंग को दूसरी स्ट्रिंग के इंडेक्स क्यू से शुरू होने और दूसरी स्ट्रिंग के इंडेक्स आर पर समाप्त होने वाले सबस्ट्रिंग के बराबर होना चाहिए।
उपरोक्त को संतुष्ट करने वाले सभी चौगुनी के भीतर q - r न्यूनतम संभव मान होना चाहिए।

हमें ऐसे चौगुनी संख्या ज्ञात करनी है।

इसलिए, यदि इनपुट firstString ='hgfn', secondString ='gfrt' जैसा है, तो आउटपुट 2 होगा।

दो चौगुनी (1, 1, 0, 0) और (2, 2, 1, 1) हैं जो शर्तों को पूरा करते हैं और q - r के लिए न्यूनतम मान रखते हैं।

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

फ़ंक्शन को परिभाषित करें ord() । इसमें ch
- ch का यूनिकोड मान लौटाएं
मुख्य विधि से निम्न कार्य करें -
बाएं:=आकार 26 की एक नई सूची जिसमें अनंत मूल्य है
दाएं:=आकार 26 की एक नई सूची जिसमें मान -1 है
res :=0
मील:=अनंत
प्रत्येक अनुक्रमणिका i, और वर्ण ch के लिए firstString, do
- बाएं[ord(ch) - ord('a')] :=न्यूनतम (बाएं[ord(ch) - ord('a')], i)
प्रत्येक अनुक्रमणिका के लिए i, और वर्ण ch सेकंडस्ट्रिंग में, करते हैं
- दायाँ[ord(ch) - ord('a') ] :=अधिकतम अधिकार[ord(ch) - ord('a') ], i
0 से 25 की सीमा में i के लिए, करें
- यदि बाएं [i] -1 के समान नहीं है, तो
  - मील:=न्यूनतम (मील, बाएँ[i] - दाएँ[i])
0 से 25 की सीमा में i के लिए, करें
- यदि बाएँ[i] अनंत के समान नहीं है और दाएँ[i] -1 के समान नहीं है, तो
  - अगर बाएँ[i] - दाएँ[i] mi के समान है, तो
    - रेस :=रेस + 1
रिटर्न रेस

उदाहरण

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

def solve(firstString, secondString):
   left = [float('inf')] * 26
   right = [-1] * 26
   res = 0
   mi = float('inf')
   for i, ch in enumerate(firstString):
      left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
   for i, ch in enumerate(secondString):
      right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
   for i in range(26):
      if left[i] != -1:
         mi = min(mi, left[i] - right[i])
   for i in range(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))

इनपुट

'hgfn', 'gfrt'