说明

LCS问题

代码

def lcs_length(X:str,Y:str)->int:
    m = len(X)
    n = len(Y)
    c = [[0] * (m+1) for _ in range(n+1)]
    b = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if X[j-1] == Y[i-1]:
                c[i][j] = c[i-1][j-1]+1
                b[i][j] = 3
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = 2
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = 1
    # 打印LCS字符串
    print_lcs(b,X,n,m)
    return c[-1][-1]
def print_lcs(b,X,i,j):
    if i == 0 or j == 0:
        return
    if b[i][j] == 3:
        print_lcs(b,X,i-1,j-1)
        print(X[j-1])
    elif b[i][j] == 2:
        print_lcs(b,X,i-1,j)
    else:
        print_lcs(b,X,i,j-1)
X = "BDCABA"
Y = "ABCBDAB"
res = lcs_length(X,Y)
print(res)