পাইথনে একটি স্ট্রিং তৈরির ন্যূনতম খরচ বের করার প্রোগ্রাম

একটি স্ট্রিং str দৈর্ঘ্য n দিয়ে তৈরি করতে হবে। দুটি অপারেশন ব্যবহার করা যায়:

1. একটি ক্যারেক্টার যোগ করা — খরচ a
2. একটি সাবস্ট্রিং যোগ করা — খরচ r

স্ট্রিং তৈরির ন্যূনতম খরচ বের করুন।

উদাহরণ

a = 5, r = 4, str = 'tpoint' → আউটপুট: 29

str = 't'   ; খরচ 5
str = 'tp'  ; খরচ 5
str = 'tpo' ; খরচ 5
str = 'tpoi'; খরচ 5
str = 'tpoin'; খরচ 5
str = 'tpoint'; সাবস্ট্রিং 't' যোগ ; খরচ 4
মোট = 29

এলগরিদম

1. largest[i] = সূচক i-তে শেষ হওয়া সাবস্ট্রিংয়ের মধ্যে যা আগে আসেছে, তার সর্বোচ্চ দৈর্ঘ্য।
2. স্লাইডিং উইন্ডো / টু-পয়েন্টার দিয়ে largest অ্যারে বানান।
3. DP অ্যারে c দিয়ে ন্যূনতম খরচ বের করুন:
   • c[0] = a
   • c[i] = min(c[i-1]+a, c[i-largest[i]]+r) (যদি largest[i] > 0)
4. c[-1] রিটার্ন করুন।

পাইথন কোড

def solve(a, r, str):
    size = len(str)
    largest = []
    low = 0
    for upp in range(1, size+1):
        while str[low:upp] not in str[:low]:
            low += 1
        largest.append(upp - low)
    c = [a]
    for i in range(1, size):
        if largest[i] == 0:
            c.append(c[-1] + a)
        else:
            c.append(min(c[-1] + a, c[i - largest[i]] + r))
    return c[-1]

print(solve(5, 4, 'tpoint'))  # আউটপুট: 29

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

5, 4, 'tpoint'
29