পাইথনে তিনটি স্ট্রিং-এর দীর্ঘতম সাধারণ অনুসৃতির দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের তিনটি স্ট্রিং s1, s2 এবং s3 আছে, আমাদের তাদের দীর্ঘতম সাধারণ অনুসারীর দৈর্ঘ্য খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s1 ="ababchemxde" s2 ="pyakcimde" s3 ="oauctime" এর মত হয়, তাহলে আউটপুট হবে 4, কারণ দীর্ঘতম সাধারণ অনুবর্তন হল "acme"৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=s1 এর আকার, n :=s2 এর আকার, o :=s3 এর আকার
dp :=আকারের একটি 3D ম্যাট্রিক্স (o + 1) x (n + 1) x (m + 1)
আমি 1 থেকে m রেঞ্জের জন্য, কর
- করুন
  - 1 থেকে o রেঞ্জের k-এর জন্য, করুন
    - যদি s1[i - 1], s2[j - 1], s3[k - 1] একই হয়, তাহলে
      - dp[i, j, k] :=1 + dp[i - 1, j - 1, k - 1]
    - অন্যথায়,
      - dp[i, j, k] =সর্বাধিক (dp[i - 1, j, k], dp[i, j - 1, k] এবং dp[i,j, k - 1])
রিটার্ন dp[m, n, o]

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, s1, s2, s3):
      m = len(s1)
      n = len(s2)
      o = len(s3)
      dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k in range(m + 1)]
      for i in range(1, m + 1):
         for j in range(1, n + 1):
            for k in range(1, o + 1):
               if s1[i - 1] == s2[j - 1] == s3[k - 1]:
                  dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
               else:
                  dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
         return dp[m][n][o]
ob = Solution()
s1 = "ababchemxde"
s2 = "pyakcimde"
s3 = "oauctime"
print(ob.solve(s1, s2, s3))

ইনপুট

"ababchemxde", "pyakcimde", "oauctime"