एक स्ट्रिंग के सबसे लंबे अनुक्रम की लंबाई ज्ञात करें जो C++ में किसी अन्य स्ट्रिंग को प्रतिस्थापित कर रहा है

मान लीजिए, हमारे पास दो स्ट्रिंग्स X और Y हैं, और हमें स्ट्रिंग X के सबसे लंबे बाद के अनुक्रम की लंबाई का पता लगाना है, जो अनुक्रम Y में है। इसलिए यदि X ="ABCD" और Y ="BACDBDCD", तो आउटपुट 3 होगा। . चूंकि "एसीडी" एक्स का सबसे लंबा उप-अनुक्रम है, जो वाई का विकल्प है।

यहां हम इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। इसलिए यदि X की लंबाई n है, और Y की लंबाई m है, तो क्रम की DP सरणी बनाएं (m+1)x(n+1)। DP का मान [i, j], X[0…j] के बाद की अधिकतम लंबाई है, जो Y[0…i] का विकल्प है। अब DP के प्रत्येक सेल के लिए, यह नीचे की तरह अनुसरण करेगा:

• i के लिए 1 से m की सीमा में:
  • जे के लिए 1 से n की सीमा में
    • जब X[i – 1] Y[j – i] के समान हो, तब DP[i, j] :=1 + DP[i – 1, j – 1]
    • अन्यथा डीपी[i, j] :=1 + DP[i, j-1]

और अंत में x के सबसे लंबे अनुवर्ती की लंबाई, जो कि y का विकल्प है, अधिकतम (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