Tìm độ dài dãy con dài nhất của chuỗi X là chuỗi con của chuỗi Y trong C++

Cho hai chuỗi X và Y. Tìm độ dài dãy con (subsequence) dài nhất của X mà cũng là chuỗi con (substring) của Y. Ví dụ: X="ABCD", Y="BACDBDCD", kết quả 3 (dãy "ACD").

Dùng quy hoạch động: DP[i][j] = độ dài dãy con dài nhất của X[0..j-1] là substring của Y[0..i-1]. Công thức:

• Nếu X[j-1] == Y[i-1]: DP[i][j] = 1 + DP[i-1][j-1]
• Ngược lại: DP[i][j] = DP[i][j-1]

Ví dụ

#include <iostream>
#define MAX 100
using namespace std;

int maxSubLength(string x, string y) {
    int table[MAX][MAX];
    int n = x.length(), 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);
}

Kết quả

Length of Maximum subsequence substring is: 3