def lcs(X, Y): # 创建一个二维数组 m = len(X) n = len(Y) L = [[None]*(n+1) for i in range(m+1)] # 填充L [i] [0] = 0 和 L [0] [j] = 0 for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L[i][j] = 0 # 填充L [i] [j]，如果X [i-1] == Y [j-1]，则L [i] [j] = L [i-1] [j-1] +1，否则L [i] [j] = max（L [i-1] [j]，L [i] [j-1]） for i in range(1, m+1): for j in range(1, n+1): if X[i-1] == Y[j-1]: L[i][j] = L[i-1][j-1] + 1 else: L[i][j] = max(L[i-1][j], L[i][j-1]) # L [m] [n]存储LCS的长度值 return L[m][n] X = "AGGTAB" Y = "GXTXAYB" print("Length of LCS is ", lcs(X, Y))修改代码，输出最长公共子序列

def lcs(X, Y):
# 创建一个二维数组
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]

# 填充L
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])

# 回溯构建LCS
lcs = []
i, j = m, n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs.append(X[i-1])
i -= 1
j -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1

# 反转字符串
lcs.reverse()

# 返回结果
return ''.join(lcs)

X = "AGGTAB"
Y = "GXTXAYB"
print("Longest Common Subsequence is ", lcs(X, Y))