Giả sử, chúng ta có hai chuỗi X và Y, và chúng ta phải tìm độ dài của chuỗi con dài nhất của chuỗi X, là chuỗi con trong chuỗi Y. Vì vậy, nếu X =“ABCD” và Y =“BACDBDCD”, thì đầu ra sẽ là 3 . Vì “ACD” là dãy con dài nhất của X, là dãy con của Y.
Ở đây chúng ta sẽ sử dụng phương pháp lập trình động để giải quyết vấn đề này. Vì vậy, nếu độ dài của X là n và độ dài của Y là m, thì hãy tạo mảng DP có thứ tự (m + 1) x (n + 1). Giá trị của DP [i, j] là độ dài lớn nhất của dãy con của X [0… j], là chuỗi con của Y [0… i]. Bây giờ đối với mỗi ô của DP, nó sẽ như sau:
- đối với tôi trong phạm vi từ 1 đến m:
- cho j trong phạm vi từ 1 đến n
- khi X [i - 1] giống với Y [j - i], thì DP [i, j]:=1 + DP [i - 1, j - 1]
- Ngược lại DP [i, j]:=1 + DP [i, j - 1]
- cho j trong phạm vi từ 1 đến n
Và cuối cùng độ dài của dãy con dài nhất của x, là chuỗi con của y là tối đa (DP [i, n]), trong đó 1 <=i <=m.
Ví dụ
#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);
} Đầu ra
Length of Maximum subsequence substring is: 3