python实现lcs算法

LCS（最长公共子序列）算法是一种常见的字符串匹配算法，可以用来求解两个字符串的最长公共子序列。下面是 Python 实现的 LCS 算法代码：

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

其中，`s1` 和 `s2` 分别是两个字符串，`m` 和 `n` 分别是它们的长度。`dp` 是一个二维数组，用来存储最长公共子序列的长度。

算法的核心是一个二重循环，它遍历 `s1` 和 `s2` 的所有字符，并根据字符是否相等更新 `dp` 数组的值。最终，`dp[m][n]` 就是两个字符串的最长公共子序列的长度。

如果需要输出最长公共子序列，可以使用回溯法，代码如下：

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j = m, n
    res = []
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            res.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(res[::-1])

这里使用了 `res` 列表来存储最长公共子序列中的字符，最后再将其反转并转化为字符串输出。