मान लीजिए, हमारे पास दो स्ट्रिंग्स X और Y हैं, और हमें स्ट्रिंग X के सबसे लंबे उपअनुक्रम की लंबाई ढूंढनी है, जो अनुक्रम Y में उपस्ट्रिंग है। इसलिए यदि X = "ABCD" और Y = "BACDBDCD", तो आउटपुट 3 होगा। क्योंकि "ACD" X का सबसे लंबा उप-अनुक्रम है, जो Y का उपस्ट्रिंग है।
यहां हम इस समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। इसलिए यदि X की लंबाई n है, और Y की लंबाई m है, तो (m+1)x(n+1) क्रम का DP सरणी बनाएं। DP[i, j] का मान X[0...j] के उपअनुक्रम की अधिकतम लंबाई है, जो Y[0...i] का उपस्ट्रिंग है। अब DP के प्रत्येक सेल के लिए, यह नीचे की तरह अनुसरण करेगा:
- i के लिए 1 से m तक की रेंज में:
- j के लिए 1 से n तक की रेंज में
- जब X[i - 1], Y[j - i] के समान हो, तो DP[i, j] := 1 + DP[i - 1, j - 1]
- अन्यथा DP[i, j] := 1 + DP[i, j - 1]
- j के लिए 1 से n तक की रेंज में
और अंत में 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
