Longest Common Subsequence (LCS) ใน Java: Dynamic Programming

Longest Common Subsequence (LCS)

หา ความยาว ของ subsequence ที่พบใน ทั้งสองสตริง (ไม่ต้องติดกัน ต้องเรียงลำดับเดียวกัน)

ตัวอย่างโค้ด (DP 2D)

public class Demo { 
    // คืนความยาว LCS
    int lcsLength(char[] a, char[] b, int m, int n) { 
        // dp[i][j] = LCS length ของ a[0..i-1] และ b[0..j-1]
        int[][] dp = new int[m + 1][n + 1]; 
        
        for (int i = 0; i <= m; i++) { 
            for (int j = 0; j <= n; j++) { 
                if (i == 0 || j == 0) { 
                    dp[i][j] = 0; // Base case: empty string
                } else if (a[i - 1] == b[j - 1]) { 
                    dp[i][j] = dp[i - 1][j - 1] + 1; // ตัวอักษรตรงกัน
                } else { 
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // ไม่ตรง 取 max
                } 
            } 
        } 
        return dp[m][n]; 
    } 
    
    public static void main(String[] args) { 
        Demo demo = new Demo(); 
        String s1 = "MNSQR"; 
        String s2 = "PSQR"; 
        
        char[] a = s1.toCharArray(); 
        char[] b = s2.toCharArray(); 
        
        System.out.println("ความยาว LCS: " + demo.lcsLength(a, b, a.length, b.length)); 
    } 
}

ผลลัพธ์

ความยาว LCS: 3

คำอธิบาย (DP Table)

s1 = "MNSQR", s2 = "PSQR"

     ''  P   S   Q   R
''   0   0   0   0   0
M    0   0   0   0   0
N    0   0   0   0   0
S    0   0   1   1   1
Q    0   0   1   2   2
R    0   0   1   2   3  <- LCS = 3 ("SQR")

LCS จริงคือ "SQR" (ความยาว 3)

ความซับซ้อน

Space Optimization: O(min(m,n))

// ใช้แค่ 2 แถว (current, previous)
public static int lcsOptimized(String s1, String s2) { 
    if (s1.length() < s2.length()) return lcsOptimized(s2, s1); 
    
    int[] prev = new int[s2.length() + 1]; 
    int[] curr = new int[s2.length() + 1]; 
    
    for (char c1 : s1.toCharArray()) { 
        for (int j = 1; j <= s2.length(); j++) { 
            if (c1 == s2.charAt(j - 1)) 
                curr[j] = prev[j - 1] + 1; 
            else 
                curr[j] = Math.max(prev[j], curr[j - 1]); 
        } 
        int[] temp = prev; prev = curr; curr = temp; // swap
    } 
    return prev[s2.length()]; 
}

การสร้าง LCS String จริง (Backtracking)

public static String buildLCS(String s1, String s2) { 
    int m = s1.length(), n = s2.length(); 
    int[][] dp = new int[m + 1][n + 1]; 
    
    // Fill DP table (same as above)
    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= n; j++) 
            dp[i][j] = (s1.charAt(i-1) == s2.charAt(j-1)) 
                ? dp[i-1][j-1] + 1 
                : Math.max(dp[i-1][j], dp[i][j-1]); 
    
    // Backtrack
    StringBuilder lcs = new StringBuilder(); 
    int i = m, j = n; 
    while (i > 0 && j > 0) { 
        if (s1.charAt(i-1) == s2.charAt(j-1)) { 
            lcs.append(s1.charAt(i-1)); 
            i--; j--; 
        } else if (dp[i-1][j] > dp[i][j-1]) { 
            i--; 
        } else { 
            j--; 
        } 
    } 
    return lcs.reverse().toString(); 
}

การประยุกต์ใช้

• Diff tools (git diff, 比較ไฟล์)
• Bioinformatics (DNA sequence alignment)
• Plagiarism detection
• Version control systems