使用python3实现LCS差分算法来计算字符串差异

下面是一个使用Python 3实现LCS（最长公共子序列）差分算法的例子：

def lcs_diff(s1, s2):
    m = len(s1)
    n = len(s2)

    # 构建LCS表
    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])

    # 回溯LCS表，找出差异部分
    diff = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            diff.append('-' + s1[i-1])
            i -= 1
        else:
            diff.append('+' + s2[j-1])
            j -= 1

    # 处理剩余的字符串
    while i > 0:
        diff.append('-' + s1[i-1])
        i -= 1
    while j > 0:
        diff.append('+' + s2[j-1])
        j -= 1

    return reversed(diff)

# 示例用法
s1 = "ABCBDAB"
s2 = "BDCAB"
diff = lcs_diff(s1, s2)
for d in diff:
    print(d)

这个例子中，我们定义了一个lcs_diff函数，它接受两个字符串s1和s2作为参数，并返回一个迭代器，该迭代器包含了将s1转换为s2所需的差异操作。

该函数首先构建了一个二维的LCS表dp，其中dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列的长度。

然后，函数从LCS表的右下角开始回溯，找出差异部分。如果s1[i-1]等于s2[j-1]，则表示这两个字符是相同的，不需要进行任何操作。如果dp[i][j]等于dp[i-1][j]，则表示s1的第i个字符需要被删除（用-表示），如果dp[i][j]等于dp[i][j-1]，则表示s2的第j个字符需要被插入（用+表示）。

最后，函数处理剩余的字符，如果有的话。最后返回一个反转后的差异操作列表。

在示例中，我们使用字符串ABCBDAB和BDCAB进行演示，输出结果为：

-B
+C
A
BD
AB
``