একটি স্ট্রিংয়ের দীর্ঘতম অনুক্রমের দৈর্ঘ্য খুঁজুন যা C++ এ অন্য স্ট্রিংয়ের সাবস্ট্রিং

ধরুন, আমাদের দুটি স্ট্রিং X এবং Y আছে, এবং আমাদের স্ট্রিং X এর দীর্ঘতম অনুসারীর দৈর্ঘ্য খুঁজে বের করতে হবে, যা Y ক্রম অনুসারে সাবস্ট্রিং। তাই যদি X =“ABCD” এবং Y =“BACDBDCD”, তাহলে আউটপুট হবে 3। যেহেতু "ACD" হল X এর দীর্ঘতম সাব-সিকুয়েন্স, যা Y এর সাবস্ট্রিং।

এখানে আমরা এই সমস্যা সমাধানের জন্য ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব। তাই যদি X-এর দৈর্ঘ্য n হয় এবং Y-এর দৈর্ঘ্য m হয়, তাহলে ডিপি অ্যারে অফ অর্ডার (m+1)x(n+1) তৈরি করুন। DP[i, j]-এর মান হল X[0…j]-এর পরের দৈর্ঘ্যের সর্বাধিক দৈর্ঘ্য, যা Y[0…i]-এর সাবস্ট্রিং। এখন DP এর প্রতিটি ঘরের জন্য, এটি নীচের মত অনুসরণ করবে:

• আমি 1 থেকে m:
  পরিসরে 1 থেকে n
  রেঞ্জের মধ্যে j-এর জন্য
  • যখন X[i – 1] Y[j – i] এর মত হয়, তখন DP[i, j] :=1 + DP[i – 1, j – 1]
  • অন্যথায় DP[i, j] :=1 + DP[i, j – 1]

এবং অবশেষে x এর দীর্ঘতম অনুসারীর দৈর্ঘ্য, যা y এর সাবস্ট্রিং হল max(DP[i, n]), যেখানে 1 <=i <=m।

উদাহরণ

#include<iostream>
#define MAX 100
using namespace std;
int maxSubLength(string x, string y) {
   int table[MAX][MAX];
   int n = x.length();
   int m = y.length();
   for (int i = 0; i <= m; i++)
      for (int j = 0; j <= n; j++)
   table[i][j] = 0;
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (x[j - 1] == y[i - 1])
            table[i][j] = 1 + table[i - 1][j - 1];
         else
            table[i][j] = table[i][j - 1];
      }
   }
   int ans = 0;
   for (int i = 1; i <= m; i++)
   ans = max(ans, table[i][n]);
   return ans;
}
int main() {
   string x = "ABCD";
   string y = "BACDBDCD";
   cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
}

আউটপুট

Length of Maximum subsequence substring is: 3