给定两个子序列X={x1,x2,x3,...,xm}和Y={y1,y2,y3,...,yn},找到一个X和Y的一个最长的公共子序列。最长公共子序列长度递归式 dp[i][j]代表区间i到j之间的最长公共子序列长度
- i=0或j=0时，dp[i][j]=0;
- i、j>0且xi=yj dp[i][j]=dp[i-1][j+1];
- i、j>0且xi！=yj dp[i][j]=max(dp[i][j-1],dp[i-1][j])
在输出的字符串的时候我们递归的方式，我们将操作储存在一个b[][]中，如果是str1[i-1]==str2[j-1],b[i][j]=1;如果dp[i][j-1]>=dp[i-1][j],b[i][j]=2,其他情况dp[i][j]=3;
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 1002
using namespace std;
int dp[N][N],b[N][N];
char str1[N],str2[N];
int len1,len2;
void LCSL(){
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1[i-1]==str2[j-1]){
dp[i][j]=dp[i-1][j-1]+1; //如果当前字符相同，则公共子序列的长度为该字符前的最长公共子序列+1
b[i][j]=1;
}
else{
if(dp[i][j-1]>=dp[i-1][j]){
dp[i][j]=dp[i][j-1];
b[i][j]=2;
}
else
{
dp[i][j]=dp[i-1][j];
b[i][j]=3;
}
}
}
}
}
void print(int i,int j){
if(i==0||j==0)return;
if(b[i][j]==1){
print(i-1,j-1);
cout<<str1[i-1];
}
else if(b[i][j]==2)
print(i,j-1);
else
print(i-1,j);
}
int main(){
while(cin>>str1>>str2){
len1=strlen(str1);
len2=strlen(str2);
memset(dp,0,sizeof(dp));
memset(b,0,sizeof(b));
/*
for(int i=0;i<=len1;i++)//初始化第一列为0
dp[i][0]=0;
for(int j=0;j<=len2;j++)//初始化第一行为0
dp[0][j]=0;
*/
LCSL();
cout<<"str1和str2的最长公共子序列长度为："<<dp[len1][len2]<<endl;
cout<<"str1和str2最长公共子序是： ";
print(len1,len2);
}
return 0;
}
/*
ABCADAB
BACDBA
str1和str2的最长公共子序列长度为：4
str1和str2最长公共子序是： BADB
*/