जब डायनामिक प्रोग्रामिंग के साथ बॉटम-अप दृष्टिकोण का उपयोग करके सबसे लंबी सामान्य सबस्ट्रिंग खोजने की आवश्यकता होती है, तो एक मेथड परिभाषित किया जा सकता है, जो छोटी समस्याओं के समाधान की गणना करता है। इन छोटी समस्या परिणामों को बार-बार गणना करने की आवश्यकता नहीं होती है। इसके बजाय, जब आवश्यक हो तो उन्हें केवल एक्सेस किया जा सकता है। यह हाथ में बड़ी समस्या का समाधान विकसित करने की ओर ले जाएगा।
उदाहरण
def compute_lcw(string_1, string_2):
val = [[-1] * (len(string_2) + 1) for _ in range(len(string_1) + 1)]
for i in range(len(string_1) + 1):
val[i][len(string_2)] = 0
for j in range(len(string_2)):
val[len(string_1)][j] = 0
lcw_i = lcw_j = -1
lcw_len = 0
for i in range(len(string_1) - 1, -1, -1):
for j in range(len(string_2)):
if string_1[i] != string_2[j]:
val[i][j] = 0
else:
val[i][j] = 1 + val[i + 1][j + 1]
if lcw_len < val[i][j]:
lcw_len = val[i][j]
lcw_i = i
lcw_j = j
return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("सबसे लंबी सामान्य सबस्ट्रिंग है: ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len])आउटपुट
सबसे लंबी सामान्य सबस्ट्रिंग है: bull
व्याख्या
- 'compute_lcw' नामक एक मेथड परिभाषित किया गया है, जो दो स्ट्रिंग्स को पैरामीटर के रूप में लेता है।
- दोनों स्ट्रिंग्स पर पुनरावृति की जाती है, और जांचा जाता है कि क्या दोनों में कोई मिलान वाली स्ट्रिंग मिली है।
- यहां तक कि जब एक सिंगल कैरेक्टर मिलता है, तो इसे दूसरे वेरिएबल में संग्रहीत किया जाता है।
- जब यह स्ट्रिंग के अंत तक चलता है, तो एक और स्ट्रिंग दोनों स्ट्रिंग्स के लिए सामान्य होगी।
- दो स्ट्रिंग्स परिभाषित की जाती हैं, और इन दो स्ट्रिंग्स को पास करके मेथड को कॉल किया जाता है।
- इस ऑपरेशन का डेटा एक वेरिएबल को असाइन किया जाता है।
- इसे फिर आउटपुट के रूप में कंसोल पर प्रदर्शित किया जाता है।
