最長共同子序列 LCS

Vibe Prompt

「幫我用 DP 找出 'abcde' 與 'ace' 的 LCS，印出 dp 表格與最長共同子序列本身。」

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 回溯
    i, j = m, n
    result = []
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], ''.join(reversed(result))

length, seq = lcs("abcde", "ace")
print(f"LCS 長度: {length}")
print(f"LCS: {seq}")

# 應用：Git Diff 比較
old = "int x = 10;"
new = "int y = 20;"
_, common = lcs(old, new)
print(f"共同部分: {common}")