Python最长公共子序列

最长公共子序列 (LCS) — 动态规划二维表求解 回溯还原广泛应用于 diff 工具和生物信息学序列比对def lcs_length(a: str, b: str) - int:返回 LCS 长度dp[i][j] a[:i] 与 b[:j] 的 LCSn, m len(a), len(b)dp [[0] * (m 1) for _ in range(n 1)]for i in range(1, n 1):for j in range(1, m 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]) # 取较大子问题return dp[n][m]def lcs_backtrack(a: str, b: str) - str:回溯还原 LCS 序列本身n, m len(a), len(b)dp [[0] * (m 1) for _ in range(n 1)]# dir: 1左上↖, 2上↑, 3左←direc [[0] * (m 1) for _ in range(n 1)]for i in range(1, n 1):for j in range(1, m 1):if a[i - 1] b[j - 1]:dp[i][j] dp[i - 1][j - 1] 1direc[i][j] 1elif dp[i - 1][j] dp[i][j - 1]:dp[i][j] dp[i - 1][j]direc[i][j] 2else:dp[i][j] dp[i][j - 1]direc[i][j] 3# 回溯res []i, j n, mwhile i 0 and j 0:if direc[i][j] 1:res.append(a[i - 1]); i - 1; j - 1elif direc[i][j] 2:i - 1else:j - 1return .join(reversed(res))def lcs_space_optimized(a: str, b: str) - int:只用两行数组求 LCS 长度空间 O(min(n,m))if len(a) len(b):a, b b, a # 确保 b 是较短的串prev [0] * (len(b) 1)for ch_a in a:curr [0] * (len(b) 1)for j, ch_b in enumerate(b, 1):if ch_a ch_b:curr[j] prev[j - 1] 1else:curr[j] max(prev[j], curr[j - 1])prev currreturn prev[len(b)]def demo():a, b ABCBDAB, BDCABAprint(f序列 A: {a})print(f序列 B: {b})print(fLCS 长度: {lcs_length(a, b)})print(fLCS 长度(空间优化): {lcs_space_optimized(a, b)})print(fLCS 序列: {lcs_backtrack(a, b)})# 验证长度与回溯结果一致lcs_str lcs_backtrack(a, b)assert len(lcs_str) lcs_length(a, b), 长度不匹配!print(一致性验证通过 ✓)if __name__ __main__:demo()