পাইথনে প্রদত্ত দুটি স্ট্রিংয়ের সাধারণ বিশেষ সাবস্ট্রিংয়ের আকার খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং s1 এবং s2 আছে। আমাদের দীর্ঘতম স্ট্রিং s3 এর আকার খুঁজে বের করতে হবে যা s1 এবং s2 উভয়েরই বিশেষ সাবস্ট্রিং৷

আমরা বলতে পারি একটি স্ট্রিং x অন্য একটি স্ট্রিং y এর বিশেষ সাবস্ট্রিং যদি y থেকে 0 বা তার বেশি অক্ষর সরিয়ে x তৈরি করা যায়।

সুতরাং, যদি ইনপুট s1 ='pineapple' s2 ='people' এর মত হয়, তাহলে আউটপুট হবে 5 কারণ বিশেষ সাবস্ট্রিং 'peple', সাইজ 5।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• পূর্ববর্তী :=একটি নতুন অভিধান, যেখানে কিছু কী উপস্থিত না থাকলে, 0 ফেরত দিন
• আমি 0 থেকে s1 - 1 এর পরিসরের জন্য,
  করুন
  • cur :=একটি নতুন অভিধান, যেখানে কিছু কী উপস্থিত না থাকলে, 0 ফেরত দিন
  j-এর জন্য 0 থেকে s2- 1 আকারের পরিসরে,
  করুন
  • cur[j] :=prev[j - 1] + 1 যখন s1[i] s2[j] এর সমান হয় অন্যথায় cur[j -1] এবং prev[j] এর সর্বাধিক
  • পূর্ববর্তী :=cur
• আগের রিটার্ন [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'

আউটপুট

5