পাইথনে দুটি স্ট্রিং-এর কমন স্পেশাল সাবস্ট্রিং-এর দৈর্ঘ্য বের করার প্রোগ্রাম

দুটি স্ট্রিং s1 এবং s2 দেওয়া আছে। এমন সবচেয়ে লম্বা স্ট্রিং s3 বের করুন যা s1 এবং s2-র দুটোই স্পেশাল সাবস্ট্রিং। স্ট্রিং x হলো y-র স্পেশাল সাবস্ট্রিং যদি y-থেকে ০ বা অধিক ক্যারেক্টার রিমুভ করে x পাওয়া যায় (অর্থাৎ LCS)।

উদাহরণ

s1 = 'pineapple', s2 = 'people' → আউটপুট: 5

LCS: 'peple' (দৈর্ঘ্য ৫)

এলগরিদম (DP - Longest Common Subsequence)

1. prev := defaultdict(int)
2. 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
3. prev[len(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))  # আউটপুট: 5

ইনপুট / আউটপুট

'pineapple', 'people'
5