Python函数实现最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是指两个序列在某个顺序下的相同的最长子序列。其中的“子序列”指的是不要求在原序列中连续的子序列。例如：

- 序列A：ACCGGTCGAGTGCGCGGAAGCCGGCCGAA

- 序列B：GTCGTTCGGAATGCCGTTGCTCTGTAAA

它们的最长公共子序列是：GTCGTCGGAAGCCGGCCGAA

Python函数实现最长公共子序列，可以通过动态规划的方法来实现。具体步骤如下：

1. 创建一个二维数组dp，其中dp[i][j]表示序列A中前i个字符和序列B中前j个字符的LCS长度。

2. 初始化 行和 列的值，使它们都等于0，因为任何一个序列和空序列的LCS都为0。

3. 对于A中的每一个字符和B中的每一个字符，比较它们是否相等。如果相等，那么dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

4. 最终dp[-1][-1]就是序列A和序列B的LCS长度。

下面是Python代码实现：

def findLCS(A, B):
    m, n = len(A), len(B)
    # 创建二维数组dp
    dp = [[0] * (n+1) for _ in range(m+1)]
    # 初始化      行和      列
    for i in range(1, m+1):
        dp[i][0] = 0
    for j in range(1, n+1):
        dp[0][j] = 0
    # 动态规划，填充dp数组
    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长度
    return dp[-1][-1]

测试一下：

A = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"
B = "GTCGTTCGGAATGCCGTTGCTCTGTAAA"
print(findLCS(A, B))  # 17

输出结果为17，说明序列A和序列B的最长公共子序列长度为17。

总结一下，Python函数实现最长公共子序列的关键是理解动态规划算法的基本思路和实现过程。在实现的过程中，注意对dp数组的初始化和循环的边界条件，同时也要注意LCS的定义和计算方式，这样才能保证算法的正确性和可靠性。