Longest Common Subsequence (LCS) ใน C++

ปัญหา

ให้ String สองตัว text1, text2 หาความยาว Longest Common Subsequence (LCS)

Subsequence = ลบบางตัวอักษรออก (อาจไม่ลบ) คงลำดับเดิม

ตัวอย่าง

text1 = "abcde", text2 = "ace" → LCS = "ace" ความยาว 3

Dynamic Programming

DP[i][j] = LCS ของ text1[0..i-1] และ text2[0..j-1]

if text1[i-1] == text2[j-1]: DP[i][j] = 1 + DP[i-1][j-1]
else: DP[i][j] = max(DP[i-1][j], DP[i][j-1])

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestCommonSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        if (!n || !m) return 0;
        
        // 1-based indexing สะดวกกว่า
        s = " " + s;
        t = " " + t;
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if (s[i] == t[j])
                    dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]);
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << ob.longestCommonSubsequence("abcde", "ace") << endl; // 3
    cout << ob.longestCommonSubsequence("abc", "def") << endl;   // 0
    return 0;
}

ผลลัพธ์

3
0

ความซับซ้อน

• Time: O(N×M)
• Space: O(N×M) → ลดเหลือ O(min(N,M)) ได้ด้วย 1D Array

Space Optimized (O(min(N,M)))

int longestCommonSubsequence(string s, string t) {
    if (s.size() < t.size()) swap(s, t); // t สั้นกว่า
    vector<int> dp(t.size() + 1), prev(t.size() + 1);
    
    for (char c : s) {
        for (int j = 1; j <= t.size(); j++) {
            if (c == t[j-1]) dp[j] = 1 + prev[j-1];
            else dp[j] = max(prev[j], dp[j-1]);
        }
        swap(dp, prev);
    }
    return prev[t.size()];
}