1.问题

最长公共子序列问题：
给定序列X=<x1,x2,x3,……xn>和Y=<y1,y2,y3,……,yn>,求X和Y的最长公共序列。

2.解析

对于字符串：ACEGHI 和 BCDEFGH
LCS二维表格

3.设计

def lcs(x, y):m = len(x) + 1n = len(y) + 1if m == 1 or n == 1:print("存在空字符串！")return -1lcs_len = numpy.zeros((m,n))for i in range(1, m):for j in range(1, n):if (x[i - 1] == y[j - 1]):lcs_len[i][j] = lcs_len[i - 1][j - 1] + 1else:max_len = lcs_len[i - 1][j]if lcs_len[i][j - 1] > lcs_len[i - 1][j]:max_len = lcs_len[i][j - 1]lcs_len[i][j] = max_leni = m - 2j = n - 2ns = ''while 1:if i == -1 or j == -1:breakif x[i] == y[j]:ns= x[i]+nsi = i - 1j = j - 1else:if lcs_len[i][j + 1] > lcs_len[i + 1][j]:i = i - 1else:j = j - 1print(ns)

4.分析

时间复杂度：O(n * m) //n和m为两条字符串的长度

5.源码

https://github.com/RussellWu728/Algorithm_Homework/blob/master/%E4%BD%9C%E4%B8%9A9%E2%80%94LCS%E7%AE%97%E6%B3%95/LCS.py