Dãy con chung dài nhất (LCS)

Cho hai chuỗi, tìm độ dài của dãy con chung dài nhất (Longest Common Subsequence - LCS). Dãy con không cần liên tiếp nhưng phải giữ thứ tự.

Sử dụng quy hoạch động với bảng longSubSeq[m+1][n+1] nơi longSubSeq[i][j] là độ dài LCS của str1[0..i-1] và str2[0..j-1].

Đầu vào và Đầu ra

Đầu vào: str1 = "AGGTAB", str2 = "GXTXAYB"
Đầu ra: Độ dài LCS = 4 (dãy con: "GTAB")

Thuật toán

1. Khởi tạo bảng (m+1) x (n+1) với hàng 0 và cột 0 = 0.
2. Duyệt i từ 1 đến m, j từ 1 đến n:
   • Nếu str1[i-1] == str2[j-1]: longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1.
   • Ngược lại: longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]).
3. Kết quả ở longSubSeq[m][n].

Ví dụ C++

#include <iostream>
using namespace std;

int max(int a, int b) { return (a > b) ? a : b; }

int longestComSs(string str1, string str2) {
    int m = str1.size(), n = str2.size();
    int longSubSeq[m+1][n+1];

    for (int i=0; i<=m; i++) {
        for (int j=0; j<=n; j++) {
            if (i == 0 || j == 0) longSubSeq[i][j] = 0;
            else if (str1[i-1] == str2[j-1]) longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
            else longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
        }
    }
    return longSubSeq[m][n];
}

int main() {
    string str1 = "AGGTAB", str2 = "GXTXAYB";
    cout << "Length of Longest Common Subsequence is: " << longestComSs(str1, str2);
}

Kết quả

Length of Longest Common Subsequence is: 4