文汇新民联合报业集团(算法收集)

文汇新民联合报业集团 这是算法收集板

最大公共子序列（Longest CommonSubstring, LCS）Python版

def lcs(x, y):
    matrix = [''] * (len(x) + 1)
    for index_x in range(len(matrix)):
        matrix[index_x] = [''] * (len(y) + 1)
    for index_x in range(1,len(x) + 1):
        for index_y in range(1,len(y) + 1):
            if x[index_x - 1] == y[index_y - 1]:#这里利用属性一
                matrix[index_x][index_y] = matrix[index_x - 1][index_y - 1] + x[index_x - 1]
            elif len(matrix[index_x][index_y - 1]) > len(matrix[index_x -1][index_y]):#这里和下面利用属性二
                matrix[index_x][index_y] = matrix[index_x][index_y - 1]
            else:
                matrix[index_x][index_y] = matrix[index_x - 1][index_y]
    return matrix[len(x)][len(y)]

来源 https://www.jianshu.com/p/a1806f2fef52