[TOC] # 最长公共子序列（LCS） 最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 ## 定义 一个数列`S`，如果分别是两个或多个已知数列的子序列，且是所有匹配此条件序列中最长的，则`S` 称为已知序列的最长公共子序列。 ## 两个序列的最长公共子序列 最长公共子序列问题存在最优子结构：这个问题可以分解成更小，更简单的“子问题”，这个子问题可以分成更多的子问题，因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的，也就是说，更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决，这样子问题的解就可以被储存起来，而不用重复计算。 ### 例子 对如下两个序列 2，3，6，5，7，2，4，3 3，4，7，1，4，3，5，2 最长公共子序列为 3，7，4，3 和最长上升子序列相同，最长公共子序列也不一定唯一。 ### 分析 对于俩个序列`S`,`T`: 1. 状态：`f[i][j]`表示S的前i位和T的前j位的最长公共子序列。 2. 转移方程：`f[i+1][j+1] = f[i][j] + 1, if S[i] == T[j], f[i+1][j+1] = max(f[i][j+1], f[i+1][j]), else` 3. 初始化：f[1][1] = (S[1] == T[1]) 4. 答案：f[S.length][T.length] 代码如下： ~~~py def LCS(S, T): n, m = len(S), len(T) f = [[0 for j in range(m+1)] for i in range(n+1)] for i in range(n): for j in range(m): if S[i] == T[j]: f[i+1][j+1] = f[i][j] + 1 else: f[i+1][j+1] = max(f[i][j+1], f[i+1][j]) return f[n][m] S = input().split() T = input().split() print(LCS(S, T)) ~~~