补充输出最长公共子序列

最长公共子序列问题是指在给定的两个序列中，找到它们的最长公共子序列。下面是一个简单的 Python 实现：

def lcs(x, y):
    m = len(x)
    n = len(y)
    # 创建一个二维数组来存储最长公共子序列的长度
    lcs_table = [[0]*(n+1) for i in range(m+1)]
 
    # 填充 lcs_table
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                lcs_table[i][j] = lcs_table[i-1][j-1] + 1
            else:
                lcs_table[i][j] = max(lcs_table[i-1][j], lcs_table[i][j-1])
 
    # 从 lcs_table 中获取最长公共子序列
    lcs_sequence = ""
    i = m
    j = n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_sequence = x[i-1] + lcs_sequence
            i -= 1
            j -= 1
        elif lcs_table[i-1][j] > lcs_table[i][j-1]:
            i -= 1
        else:
            j -= 1
 
    return lcs_sequence

该函数接受两个字符串作为参数，并返回它们的最长公共子序列。函数使用动态规划算法来解决该问题，其时间复杂度为 $O(mn)$，其中 $m$ 和 $n$ 分别是两个字符串的长度。