动态规划 - 最长公共子序列和最长公共子串

基本概念

最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿。

什么是子序列呢？即一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。

什么是子串呢？给定串中任意个连续的字符组成的子序列称为该串的子串。

上图，给定的字符序列： {a,b,c,d,e,f}，它的子序列示例： {a,c,e,f} 即元素b,d被去掉后，保持原有的元素序列所得到的结果就是子序列。同理，{a,f},{c,d,e}等都是它的子序列。

它的字串示例：{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理，{a,b,c,d},{e,f}等都是它的字串。

这个问题说明白后，最长公共子序列（以下都简称LCS）就很好理解了。

给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}，s1和s2的相同子序列，且该子序列的长度最长，即是LCS。 s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

最长公共子序列LCS动态规划状态转移方程式

最长公共子序列动态规划解法

dp[i][j] -- 表示子串A[0...i]（数组长度为n）和子串B[0...j]（数组长度为m）的最长公共子序列

当A[i] == B[j]时，dp[i][j] = dp[i-1][j-1] + 1;

否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

最优解为dp[n-1][m-1];

代码实现

/*
算法解析：
由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m * n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m * n)。
*/
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001],s1[2001],s2[2001],n;
int main()
{
	/*dp[i][j]表示两个串从头开始，直到第一个串的第i位 
   和第二个串的第j位最多有多少个公共子元素 */
   	cin>>n;
   	for(int i=1;i<=n;i++) cin>>s1[i];
   	for(int i=1;i<=n;i++) cin>>s2[i];
   // 最长公共子序列LCS动态规划状态转移方程式 
   	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	     {
	     	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	     	if(s1[i]==s2[j])
	     		dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); 
	     }
   cout<<dp[n][n];
   return 0;
}

最长公共子序列的回溯过程：

最长公共子串的动态规划的状态转移方程式

最长公共子串的代码实现

#include <bits/stdc++.h>
using namespace std;
//最长公共子串 
int main(){
	string s1,s2;
	cin>>s1>>s2;
	if(s1.size() > s2.size()) //以短的作为s1
		swap(s1,s2);
	int len1 = s1.size(), len2 = s2.size();
	int start = 0, mx = 0; //记录结果
	vector<vector<int> > dp(len1+1,vector<int>(len2+1,0));
	for(int i = 1;i<=len1;i++){
		for(int j = 1;j<=len2;j++){
			if(s1[i-1] == s2[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			if(dp[i][j] > mx){
				mx = dp[i][j];
				start = i - mx;
			}
		}
	}
	cout<<s1.substr(start,mx);
	return 0;
}