যখন বটম-আপ অ্যাপ্রোচ সহ ডায়নামিক প্রোগ্রামিং ব্যবহার করে দীর্ঘতম সাধারণ সাবস্ট্রিং খুঁজে বের করার প্রয়োজন হয়, তখন একটি পদ্ধতি সংজ্ঞায়িত করা যেতে পারে, যা ছোট সমস্যার সমাধান গণনা করে। এই ছোট সমস্যার ফলাফলগুলি বারবার গণনা করার দরকার নেই। পরিবর্তে, প্রয়োজন হলেই সেগুলি অ্যাক্সেস করা যেতে পারে। এটি হাতে থাকা বড় সমস্যাটির সমাধানের দিকে নিয়ে যাবে৷
নীচে একই −
এর জন্য একটি প্রদর্শন রয়েছে৷উদাহরণ
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’ নামের একটি পদ্ধতি সংজ্ঞায়িত করা হয়েছে, যা প্যারামিটার হিসেবে দুটি স্ট্রিং নেয়।
- দুটি স্ট্রিং বারবার করা হয়, এবং উভয়ের মধ্যে কোনো মিল স্ট্রিং পাওয়া যায় কিনা তা পরীক্ষা করা হয়।
- এমনকি যখন একটি একক অক্ষর পাওয়া যায়, এটি অন্য পরিবর্তনশীলে সংরক্ষিত হয়।
- যখন এটি স্ট্রিংয়ের শেষ পর্যন্ত চলে, তখন এই দুটি স্ট্রিংয়ের জন্য অন্য একটি স্ট্রিং সাধারণ হবে৷
- দুটি স্ট্রিং সংজ্ঞায়িত করা হয়েছে, এবং এই দুটি স্ট্রিংকে পাস করে পদ্ধতি বলা হয়।
- এই অপারেশনের ডেটা একটি ভেরিয়েবলের জন্য বরাদ্দ করা হয়৷ ৷
- এটি তারপর কনসোলে আউটপুট হিসাবে প্রদর্শিত হয়।
