पायथन में दो दिए गए स्ट्रिंग्स के सामान्य विशेष सबस्ट्रिंग का आकार खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो तार s1 और s2 हैं। हमें सबसे लंबी स्ट्रिंग s3 का आकार खोजना है जो s1 और s2 दोनों का विशेष विकल्प है।

हम कह सकते हैं कि एक स्ट्रिंग x दूसरे स्ट्रिंग y का विशेष विकल्प है यदि x को y से 0 या अधिक वर्णों को हटाकर उत्पन्न किया जा सकता है।

इसलिए, यदि इनपुट s1 ='अनानास' s2 ='लोग' जैसा है, तो आउटपुट 5 होगा क्योंकि विशेष सबस्ट्रिंग 'peple', आकार 5 है।

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

पिछला :=एक नया शब्दकोश, जहां अगर कुछ कुंजी मौजूद नहीं है, तो 0 लौटाएं
i के लिए 0 से लेकर s1 - 1 के आकार तक के लिए
- cur :=एक नया शब्दकोश, जहां अगर कुछ कुंजी मौजूद नहीं है, तो 0 लौटाएं
- जे के लिए 0 से लेकर s2-1 के आकार तक के लिए
  - cur[j] :=prev[j - 1] + 1 जब s1[i] s2[j] के समान हो अन्यथा अधिकतम cur[j -1] और prev[j]
- पिछला :=वक्र
वापसी पिछला [s2 -1 का आकार]

उदाहरण

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

from collections import defaultdict
def solve(s1, s2):
   prev = defaultdict(int)
   for i in range(len(s1)):
      cur = defaultdict(int)
      for j in range(len(s2)):
         cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
      prev = cur
   return prev[len(s2)-1]

s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))

इनपुट

'pineapple', 'people'