पायथन में दी गई स्ट्रिंग बनाने की न्यूनतम लागत निर्धारित करना

मान लीजिए, हमें लंबाई n की एक स्ट्रिंग 'str' बनानी है। स्ट्रिंग बनाने के लिए, हम दो ऑपरेशन कर सकते हैं।

लागत a पर str के अंत में एक अक्षर जोड़ा जा सकता है।
लागत r पर str के अंत में एक सबस्ट्रिंग sub_str जोड़ा जा सकता है।

हमें स्ट्रिंग str बनाने की न्यूनतम लागत की गणना करनी है।

उदाहरण के लिए, यदि इनपुट है a = 5, r = 4, str = 'tpoint', तो आउटपुट होगा 29।

स्ट्रिंग 'tpoint' बनाने की लागत नीचे वर्णित है:

str = 't'; एक नया अक्षर जोड़ा गया, इसलिए लागत 5 है।
str = 'tp'; एक नया अक्षर जोड़ा गया, इसलिए लागत 5 है।
str = 'tpo'; एक नया अक्षर जोड़ा गया, इसलिए लागत 5 है।
str = 'tpoi'; एक नया अक्षर जोड़ा गया, इसलिए लागत 5 है।
str = 'tpoin'; एक नया अक्षर जोड़ा गया, इसलिए लागत 5 है।
str = 'tpoint'; सबस्ट्रिंग 't' जोड़ा गया, इसलिए लागत 4 है।

कुल लागत = 5 + 5 + 5 + 5 + 5 + 4 = 29।

समाधान दृष्टिकोण

यह समस्या डायनामिक प्रोग्रामिंग और स्ट्रिंग मिलान का उपयोग करती है। प्रत्येक पोजीशन के लिए, हम सबसे लंबा सबस्ट्रिंग ढूंढते हैं जिसे पहले बने भाग से कॉपी किया जा सकता है।

largest ऐरे की गणना करें जहां largest[i] इंडेक्स i पर समाप्त होने वाला सबसे लंबा सबस्ट्रिंग है जो पहले के भाग में मौजूद है।
डायनामिक प्रोग्रामिंग ऐरे c बनाएं जहां c[i] पहले i+1 अक्षर बनाने की न्यूनतम लागत है।
प्रत्येक पोजीशन के लिए, या तो एक अक्षर जोड़ें (लागत a) या सबसे लंबे मिलान वाले सबस्ट्रिंग को कॉपी करें (लागत r)।

पायथन कार्यान्वयन

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'))

इनपुट

5, 4, 'tpoint'