一、代碼

def lcs(string1, string2):
    len1 = len(string1)
    len2 = len(string2)
    # dp[i][j]表示string1前i位子串與string2前j位子串的最長公共子序列的長度
    dp = [[0 for j in range(len2 + 1)] for i in range(len1 + 1)]
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if string1[i - 1] == string2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 返回dp數(shù)組和最長公共子序列的長度
    return dp, dp[len1][len2]


def get_all_lcs(string1, string2, dp, i, j, dest_set, cs):
    """
    根據(jù)dp逆推出所有string1和string2的最長公共子序列
    :param string1:
    :param string2:
    :param dp: lcs(string1, string2) 返回的dp數(shù)組
    :param i: 從string1的第i位逆推
    :param j: 從string2的第j位逆推
    :param dest_set: 保存所有最長公共子序列的set
    :param cs: 當前逆推階段的公共子序列
    :return:
    """
    # 逆推完畢
    if dp[i][j] == 0:
        dest_set.add(cs)
        return
    # 若當前逆推階段兩字符相等
    if string1[i - 1] == string2[j - 1]:
        cs = string1[i - 1] + cs
        get_all_lcs(string1, string2, dp, i - 1, j - 1, dest_set, cs)
    # 若兩字符不等，需要選擇正確逆推路徑
    # 由于lcs中，兩字符不相等時dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 應(yīng)當選擇dp[i - 1][j], dp[i][j - 1]中較大的那個最為逆推路徑
    # 若dp[i - 1][j], dp[i][j - 1]相等，則分別逆推兩條路徑
    else:
        if dp[i][j - 1] > dp[i - 1][j]:
            get_all_lcs(string1, string2, dp, i, j - 1, dest_set, cs)
        elif dp[i][j - 1] < dp[i - 1][j]:
            get_all_lcs(string1, string2, dp, i - 1, j, dest_set, cs)
        else:
            get_all_lcs(string1, string2, dp, i, j - 1, dest_set, cs)
            get_all_lcs(string1, string2, dp, i - 1, j, dest_set, cs)


s1 = "12377861542"
s2 = "65435782"
dp, max_len = lcs(s1, s2)
print(max_len)

all_lcs = set()
get_all_lcs(s1, s2, dp, len(s1), len(s2), all_lcs, "")
print(all_lcs)

2、運行結(jié)果

4
{'6542', '3782'}