一、问题描述

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

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

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

LCS(X,Y)="BBCD"
 

python">from audioop import reversedef 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] + 1else: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] + 1b[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], bdef 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 -= 1j -= 1elif b[i][j] == '↑':i -= 1else :j -= 1return ''.join(reversed(res))print(lcs_trac('SGYV','SGYUY'))

二、结果展示

python">[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