最长公共子序列lcs实现

def lcs(s1, s2):
    m = len(s1)         # 记录s1长度
    n = len(s2)         # 记录s2长度
    a = [[0 for j in range(n+1)]for i in range(m+1)]        # 得分数组
    b = [[0 for j in range(n+1)]for i 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]:          # 当前字符相同，左上对角加1
                a[i][j] = a[i-1][j-1] + 1
                b[i][j] = 1
            elif a[i][j-1] > a[i-1][j]:     # 之前最长序列由左边得到
                a[i][j] = a[i][j-1]
                b[i][j] = 2
            else:
                a[i][j] = a[i-1][j]         # 之前最长序列由上边得到
                b[i][j] = 3
    return a[m][n], b                       # 返回公共序列的长度及方向矩阵

def lcs_traceback(s1, s2):
    """ 路径回溯
    :param s1:
    :param s2:
    :return:
    """
    a, b = lcs(s1, s2)
    i = len(s1)
    j = len(s2)
    res = []
    while i > 0 and j > 0:      # 有一个字符为0时，循环停止
        if b[i][j] == 1:
            res.append(s1[i-1]) # 能够取到的下标是i-1
            i -= 1
            j -= 1
        elif b[i][j] == 2:
            j -= 1
        else:
            i -= 1
    print(b)
    print("{}".format(list(reversed(res))))


if __name__ == ‘__main__‘:
    lcs_traceback("abcde", "bcdfe")