जब बॉटम-अप दृष्टिकोण के साथ डायनेमिक प्रोग्रामिंग का उपयोग करके सबसे लंबे समय तक सामान्य सबस्ट्रिंग को खोजने की आवश्यकता होती है, तो एक विधि को परिभाषित किया जा सकता है, जो छोटी समस्याओं के समाधान की गणना करता है। इन छोटे समस्या परिणामों की बार-बार गणना करने की आवश्यकता नहीं है। इसके बजाय, आवश्यकता पड़ने पर ही उन्हें एक्सेस किया जा सकता है। इससे हाथ में बड़ी समस्या का समाधान विकसित होगा।
नीचे उसी के लिए एक प्रदर्शन है -
उदाहरण
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("The longest common substring is : ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len]) आउटपुट
The longest common substring is : bull
स्पष्टीकरण
- 'compute_lcw' नाम की एक विधि परिभाषित की गई है, जो पैरामीटर के रूप में दो स्ट्रिंग लेती है।
- दो स्ट्रिंग्स को पुनरावृत्त किया जाता है, और यह देखने के लिए जाँच की जाती है कि क्या उन दोनों में कोई मेल खाने वाली स्ट्रिंग पाई जाती है।
- यहां तक कि जब एक वर्ण मिल जाता है, तब भी वह दूसरे चर में संग्रहीत होता है।
- जब यह स्ट्रिंग के अंत तक चलता है, तो इन दोनों स्ट्रिंग्स के लिए एक और स्ट्रिंग समान होगी।
- दो स्ट्रिंग्स को परिभाषित किया गया है, और इन दो स्ट्रिंग्स को पास करके मेथड को कॉल किया जाता है।
- इस ऑपरेशन का डेटा एक वैरिएबल को असाइन किया गया है।
- फिर इसे कंसोल पर आउटपुट के रूप में प्रदर्शित किया जाता है।