如何恢復最長公共子序列

最長公共子序列（Longest Common Subsequence, LCS）問題是在兩個或更多序列中找到最長的公共子序列。這裡有一個簡單的算法來恢復兩個序列的LCS：

1. 使用動態規劃算法來找到兩個序列的LCS的長度。
2. 使用回溯法來找到實際的LCS。

下面是一個簡單的Python實現：

def lcs(seq1, seq2):
    m, n = len(seq1), len(seq2)
    lcs_length = 0

    # Create a table to store the lengths of LCS of prefixes of X and Y
    lcs_lengths = [[0 for col in range(n)] for row in range(m)]

    # Fill the lcs_lengths table in bottom-up manner
    for i in range(m):
        for j in range(n):
            if seq1[i] == seq2[j]:
                lcs_lengths[i][j] = lcs_length + 1
                if i > 0 and j > 0:
                    lcs_lengths[i][j] = max(lcs_lengths[i][j], lcs_lengths[i-1][j-1])
                lcs_length = lcs_lengths[i][j]
            else:
                lcs_lengths[i][j] = 0

    # The value in lcs_lengths[m-1][n-1] is the length of LCS
    return lcs_lengths[m-1][n-1]

def restore_lcs(seq1, seq2, lcs_length):
    lcs = []
    i, j = len(seq1) - 1, len(seq2) - 1
    while i >= 0 and j >= 0:
        if seq1[i] == seq2[j]:
            lcs.insert(0, seq1[i])
            i -= 1
            j -= 1
        elif lcs_lengths[i][j] == lcs_lengths[i-1][j] or lcs_lengths[i][j] == lcs_lengths[i][j-1]:
            i -= 1
        else:
            j -= 1

    return lcs

# Example usage:
seq1 = "ABCDGH"
seq2 = "AEDFHR"
lcs_length = lcs(seq1, seq2)
print("The length of the LCS is:", lcs_length)
lcs = restore_lcs(seq1, seq2, lcs_length)
print("The LCS is:", lcs)

這個算法的時間複雜度是O(mn)，其中m和n是兩個序列的長度。空間複雜度也是O(mn)，因為我們需要一個大小為m*n的表來存儲動態規劃的狀態。