หา Longest Common Subsequence (LCS)

Longest Common Subsequence (LCS) คือ subsequence ที่ปรากฏในทั้งสองสตริง/อาร์เรย์ที่กำหนด เรียงลำดับเดียวกัน (ไม่จำเป็นต้องติดกัน)

ปัญหานี้มี Overlapping Subproblems ทำให้ Dynamic Programming เหมาะสม ใช้ตาราง 2 มิติเก็บความยาว LCS ของ prefix ต่างๆ

ตัวอย่าง Input และ Output

Input: 
String 1: "AGGTAB"
String 2: "GXTXAYB"

Output: ความยาว LCS = 4
LCS: "GTAB" (ตัวอักษรที่ขีดเส้นใต้อยู่ในทั้งสองสตริงและเรียงลำดับถูกต้อง)

อัลกอริทึม Dynamic Programming

ฟังก์ชัน longestComSubSeq(str1, str2)

ขั้นตอน:

1. สร้างตาราง longSubSeq[m+1][n+1] โดย m = len(str1), n = len(str2)
2. เติมแถวแรกและคอลัมน์แรกเป็น 0 (base case: สตริงว่าง)
3. สำหรับ i = 1 ถึง m, j = 1 ถึง n:
   • ถ้า str1[i-1] == str2[j-1] → longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1
   • ถ้าไม่เท่ากัน → longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1])
4. คำตอบอยู่ที่ longSubSeq[m][n]

ตัวอย่างโค้ด C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int longestComSs(string str1, string str2) {
    int m = str1.size();
    int 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";
    string str2 = "GXTXAYB";
    cout << "Length of Longest Common Subsequence is: " 
         << longestComSs(str1, str2);
    return 0;
}

Output

Length of Longest Common Subsequence is: 4

ความซับซ้อน

• Time: O(m × n)
• Space: O(m × n) (สามารถลดเหลือ O(min(m,n)) ได้)

การสร้าง LCS จริง (Reconstruction)

เดินย้อนกลับจาก longSubSeq[m][n]: - ถ้า str1[i-1] == str2[j-1] → เพิ่มตัวอักษรนี้ แล้วไป (i-1, j-1) - ไม่เช่นนั้น ไปทางที่มีค่ามากกว่าระหว่าง (i-1, j) และ (i, j-1)