一、问题描述

一个序列的子序列是在该序列中删去若干元素后得到的序列。例:“ABCD”和“BDF”都是“ABCDEFG”的子序列。

最长公共子序列(LCS)问题:给定两个序列X和Y，求X和Y长度最大的公共子序列

例:X="ABBCBDE" Y="DBBCDB"

LCS(X,Y)="BBCD"
 

from audioop import reverse


def lcs_lenght(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    for _ in c:
        print(_)
    return c[m][n]

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    b = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m+1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = '↖'
            elif c[i - 1][j] > c[i][j - 1]:
                c[i][j] = c[i-1][j]
                b[i][j] = '↑'
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = '←'

    for _ in c:
        print(_)
    for _ in b:
        print(_)
    return c[m][n], b

def lcs_trac(x, y):
    c, b =lcs(x, y)
    i = len(x)
    j = len(y)
    res = []
    while i > 0 and j > 0:
        if b[i][j] == '↖':
            res.append(x[i-1])
            i -= 1
            j -= 1
        elif b[i][j] == '↑':
            i -= 1
        else :
            j -= 1
    return ''.join(reversed(res))




print(lcs_trac('SGYV','SGYUY'))

二、结果展示

[0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2]
[0, 1, 2, 3, 3, 3]
[0, 1, 2, 3, 3, 3]
[0, 0, 0, 0, 0, 0]
[0, '↖', '←', '←', '←', '←']
[0, '↑', '↖', '←', '←', '←']
[0, '↑', '↑', '↖', '←', '↖']
[0, '↑', '↑', '↑', '←', '←']
SGY