পাইথন প্রোগ্রাম: ডাইনামিক প্রোগ্রামিং এবং বটম-আপ পদ্ধতিতে লংগেস্ট কমন সাবস্ট্রিং বের করা

লংগেস্ট কমন সাবস্ট্রিং (ডাইনামিক প্রোগ্রামিং)

যখন ডাইনামিক প্রোগ্রামিং এবং বটম-আপ পদ্ধতিতে লংগেস্ট কমন সাবস্ট্রিং বের করতে হয়, তখন একটি মেথড সংজ্ঞায়িত করা যেতে পারে যা ছোট ছোট সমস্যা들의 সমাধান কম্পিউট করে। এই ছোট সমস্যা들의 ফলাফলগুলো বারবার কম্পিউট করার প্রয়োজন নেই। বরং প্রয়োজনে সেগুলো অ্যাক্সেস করা যাবে। এভাবে বড় সমস্যার সমাধান তৈরি করা যাবে।

উদাহরণ

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