最长公共子序列(LCS)

最长公共子序列+模板

定义

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。一个序列S，如果分别是两个或多个已知的序列的子序列，并且是所有子序列中最长的，则称序列S为最长公共子序列。

如序列1 2 3 4 5 6 7 8和序列5 6 7 8 1 2 3 4，他们的最长公共子序列为1 2 3 4和5 6 7 8，其长度为4，由此可知，最长公共子序列也唯一，但长度唯一。

最长公共子序列，可以识别两段文字之间的“相似度”，即查重。

解法

动态规划$O(nm)$

最长公共子序列问题具有最优子结构和重复子问题，因此可以考虑动态规划。

设$C[i,j] = LCS(a[1...i],b[1...j])$，$C[i,j]$表示序列a和b的长度分为i和j时的最长公共子序列的长度，则$C[n,m]$就是序列a和b的最长公共子序列。

**状态表示：**dp[i][j] 为序列a到i位置和序列b到j位置时的最长公共子序列。

状态转移： $dp[i][j] = \begin{cases} dp[i-1][j-1]+1 &, a[i] = b[j] \\ max(dp[i-1][j],dp[i][j-1]) & ,a[i] ≠ b[j] \end{cases}$

for (int i = 1;i <= n;i ++) 
	for (int j = 1;j <= m;j ++) 
		if (a[i] == b[j])	dp[i][j] = dp[i - 1][j - 1] + 1;
		else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);