请说明如何修改算法 LCS，使它输出最长公共子序列

最长公共子序列（LCS）是两个序列中都存在的最长子序列。为了修改算法 LCS 使其输出最长公共子序列，我们需要在 LCS 算法的基础上进行一些修改，具体步骤如下：

1. 构造一个二维数组 dp，其中 dp[i][j] 表示序列 A 中前 i 个元素和序列 B 中前 j 个元素的最长公共子序列长度。

2. 初始化 dp 数组的第一行和第一列，即 dp[0][j] 和 dp[i][0] 均为 0。

3. 对于序列 A 和序列 B 中的每一个元素，判断它们是否相等。

4. 如果 A[i] 和 B[j] 相等，则 dp[i][j] = dp[i-1][j-1] + 1。

5. 如果 A[i] 和 B[j] 不相等，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

6. 最终，最长公共子序列的长度为 dp[m][n]，其中 m 和 n 分别为序列 A 和序列 B 的长度。

7. 根据 dp 数组求出最长公共子序列。从 dp[m][n] 开始，如果 A[i] 和 B[j] 相等，则将该元素加入最长公共子序列中，然后向左上方移动一格，即 i--，j--；如果不相等，则向较大的方向移动一格。

代码如下：

def LCS(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n+1) for _ in range(m+1)] # 构造二维数组
    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 = ''
    i, j = m, n
    while i > 0 and j > 0:
        if A[i-1] == B[j-1]:
            lcs = A[i-1] + lcs
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return lcs

该算法的时间复杂度为 $O(mn)$，其中 m 和 n 分别为序列 A 和序列 B 的长度。