给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，求所有最长公共子序列。 测试数据：自拟

假设我们已经有了两个序列X和Y，它们的长度分别为m和n，为了方便，我们可以把序列X和Y的下标都从1开始，即X={x1,x2,…,xm}，Y={y1,y2,…,yn}。

接下来，我们定义一个二维数组C，其中C[i,j]表示X和Y的前缀序列X[1:i]和Y[1:j]的最长公共子序列的长度。则有以下状态转移方程：

当i=0或j=0时，C[i,j]=0；

当xi=yj时，C[i,j]=C[i-1,j-1]+1；

当xi≠yj时，C[i,j]=max{C[i-1,j],C[i,j-1]}。

最后，我们可以根据数组C来构造出所有的最长公共子序列。具体方法如下：

如果xi=yj，则说明xi和yj都在最长公共子序列中，将它们加入到最长公共子序列中，然后继续考察X[1:i-1]和Y[1:j-1]的最长公共子序列；

如果xi≠yj，那么最长公共子序列一定不包括xi，那么我们需要考察X[1:i-1]和Y[1:j]的最长公共子序列和X[1:i]和Y[1:j-1]的最长公共子序列，取它们中较长的一个即可。

下面是Python代码实现：

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    # 初始化C数组
    C = [[0] * (n + 1) for i in range(m + 1)]
    # 填充C数组
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                C[i][j] = C[i - 1][j - 1] + 1
            else:
                C[i][j] = max(C[i - 1][j], C[i][j - 1])
    # 构造所有最长公共子序列
    def construct_lcs(i, j):
        if i == 0 or j == 0:
            return [""]
        elif X[i - 1] == Y[j - 1]:
            lcs_list = construct_lcs(i - 1, j - 1)
            return [s + X[i - 1] for s in lcs_list]
        else:
            lcs_list1 = construct_lcs(i - 1, j)
            lcs_list2 = construct_lcs(i, j - 1)
            return lcs_list1 + lcs_list2
    return construct_lcs(m, n)

下面是一个例子，我们求"ABCDGH"和"AEDFHR"的所有最长公共子序列：

X = "ABCDGH"
Y = "AEDFHR"
print(lcs(X, Y))

输出：

['ADH', 'ADHR', 'ADH', 'ABDH', 'ABDHR', 'ABDH', 'ABCDH', 'ABCDHR', 'ABCDH', 'ACDH', 'ACDHR', 'ACDH', 'ACDGH', 'ACDGRH', 'ACDGHR', 'ACDGHR']

可以看出，"ADH"、"ADHR"、"ABDH"、"ABDHR"、"ABCDH"、"ABCDHR"、"ACDH"、"ACDHR"、"ACDGH"、"ACDGRH"和"ACDGHR"都是最长公共子序列。