โปรแกรม C++ หาลำดับย่อยร่วมที่ยาวที่สุด (Longest Common Subsequence)

ลำดับย่อย (Subsequence) คือลำดับที่มีลำดับของชุดองค์ประกอบเหมือนกัน สำหรับลำดับ "stuv" ลำดับย่อยคือ "stu", "tuv", "suv" ฯลฯ

สำหรับสตริงความยาว n จะมีวิธาสร้างลำดับย่อยได้ 2ⁿ วิธี

ตัวอย่าง

ลำดับย่อยร่วมที่ยาวที่สุดสำหรับสตริง "ABCDGH" และ "AEDFHR" มีความยาว 3

#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("Length of LCS is %d\n", lcs(X, Y, m, n));
    return 0;
}

ผลลัพธ์

Length of LCS is 4