Chương trình C++ tìm dãy con chung dài nhất (LCS)

Dãy con (subsequence) là dãy giữ nguyên thứ tự của tập phần tử. Với dãy "stuv", các dãy con là "stu", "tuv", "suv", v.v.

Với chuỗi độ dài n, có 2ⁿ cách tạo dãy con từ chuỗi đó.

Ví dụ

Dãy con chung dài nhất của hai chuỗi "ABCDGH" và "AEDFHR" có độ dài 3.

Ví dụ mã C++

#include <iostream> 
#include <string.h> 
using namespace std; 

int max(int a, int b); 

int lcs(char* X, char* Y, int m, int n) { 
    if (m == 0 || n == 0) 
        return 0; 
    if (X[m - 1] == Y[n - 1]) 
        return 1 + lcs(X, Y, m - 1, n - 1); 
    else 
        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n)); 
} 

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

int main() { 
    char X[] = "AGGTAB"; 
    char Y[] = "GXTXAYB"; 
    int m = strlen(X); 
    int n = strlen(Y); 
    printf("Độ dài LCS là %d\n", lcs(X, Y, m, n)); 
    return 0; 
}

Kết quả

Độ dài LCS là 4