最长公共子序列（LCS）——python回溯

输入：

第一行：字符串w1

第二行：字符串w2

w1和w2长度小于等于1000

输出：

输出最长的子序列和它的长度

w1 = "" # 矩阵行，有len(w1)行
w2 = "" # 矩阵列，有len(w2)列
a = [] # 存放一种子序列（w1,w2相同字符在w2中的索引）
A = [] # 存放所有的子序列
best_a = [] # 存放最长的子序列
best_len_a = 0 # 最长子序列的长度

# 冲突检测
def conflict(k):
    global w1, w2, a, A, best_a, best_len_a
    # 如果两个字符不相等，冲突
    if a[-1] < len(w2) and w1[k] != w2[a[-1]]:
        return True
    # 如果两个字符相等，但是索引比前一个小，则冲突
    if w1[k] == w2[a[-1]] and (len(a) >= 2 and a[-1] <= a[-2]):
        return True
    # 如果部分解的长度加上后面w1的长度小于best_len_a
    if len(a) + len(w1[k:]) < best_len_a:
        return True
    return False

# 遍历第K行
def LCS(k):
    global w1, w2, a, A, best_a, best_len_a
    # 如果已经遍历完w1一次,则更新A和最长子序列一次
    if k == len(w1):
        A.append(a[:])
        if len(a) >= best_len_a:
            best_a = a[:]
            best_len_a = len(a)
    else:
        for i in range(len(w2) + 1):
            if i == len(w2):
                LCS(k + 1)
            else:
                a.append(i)
                if not conflict(k): # 剪枝
                    LCS(k + 1)
                a.pop() # 回溯

if __name__ == "__main__":
    w1 = input("请输入第1个字符：")
    w2 = input("请输入第2个字符：")
    LCS(0)
    print("最长子序列为：", "".join([ w2[i] for i in best_a]))
    print("其长度为：", best_len_a)

输出结果：

请输入第1个字符：belongs
请输入第2个字符：cnblogs
最长子序列为： blogs
其长度为： 5