LCS Longest Common Subsequence Visualization - Dynamic Programming

The Longest Common Subsequence (LCS) problem finds the longest subsequence common to two sequences. Subsequences don't need to be contiguous but must maintain relative order. LCS is fundamental to text comparison and bioinformatics.

Dynamic Programming Approach

Let dp[i][j] represent the LCS length of first i chars of A and first j chars of B.

If A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (match, LCS length +1)
If A[i-1] != B[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take max of left/top)

dp[m][n] is the LCS length. Backtrack through the DP table to reconstruct the actual LCS.

Time and Space Complexity

Metric	Complexity	Description
Time Complexity	O(M × N)	Need to fill entire DP table
Space Complexity	O(M × N)	Need to store DP table
Optimized Space	O(min(M,N))	Store only two rows (if only length needed)

Applications

Text comparison: diff tools for file comparison
Bioinformatics: DNA/protein sequence alignment
Version control: Detecting code changes
Spell checking: Basis for edit distance
Data deduplication: Identifying similar content

Text Comparison DNA Alignment Version Control Similarity

Implementation

def lcs(a, b):
    """计算最长公共子序列"""
    m, n = len(a), len(b)
    
    # 创建DP表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # 回溯获取LCS字符串
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            lcs_str.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs_str))


# 使用示例
a = "ABCBDAB"
b = "BDCABA"
result = lcs(a, b)
print(f"LCS: {result}, 长度: {len(result)}")
# 输出: LCS: BCBA, 长度: 4

public class LCS {
    
    /**
     * 计算最长公共子序列
     */
    public static String lcs(String a, String b) {
        int m = a.length();
        int n = b.length();
        
        // 创建DP表
        int[][] dp = new int[m + 1][n + 1];
        
        // 填充DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(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]);
                }
            }
        }
        
        // 回溯获取LCS字符串
        StringBuilder lcsStr = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                lcsStr.insert(0, a.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return lcsStr.toString();
    }
    
    public static void main(String[] args) {
        String a = "ABCBDAB";
        String b = "BDCABA";
        String result = lcs(a, b);
        System.out.println("LCS: " + result + 
            ", 长度: " + result.length());
        // 输出: LCS: BCBA, 长度: 4
    }
}