最长公共子序列（仅借助数组dp本身在O(m+n)时间内构造最长公共子序列）

算法课上机作业，想复杂了。。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 改进LCS函数，不使用数组b而仅借助数组c本身在O(m+n)时间内构造最长公共子序列。

原来的代码：

void LCSLength(char *x ,char *y,int m,int n, int **c, int **b)
{int i ,j;for (i = 1; i <= m; i++) c[i][0] = 0;for (i = 1; i <= n; i++) c[0][i] = 0;for (i = 1; i <= m; i++)for (j = 1; j <= n; j++){if (x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if (c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{    c[i][j]=c[i][j-1];b[i][j]=3;}}
}
void LCS(int i ,int j, char *x ,int **b)
{if (i ==0 || j==0) return;if (b[i][j]== 1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}else if (b[i][j]== 2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);
}

在打印最后结果的时候，不再使用b[][]数组进行标记。其实也很简单，在打印函数中对b[][]状态判断的时候，再重新看作dp之间的比较即可。

注意在求LCS时不要用max求，因为如果两个参数相等时并不知道选择了哪一个。代码如下：

#include
#include<string>
#include
#include
using namespace std;
int dp[200][200];
string s1,s2;
int len1,len2;
void print(int i,int j) //打印路径 
{if(i==0||j==0)return ;if(s1[i-1]==s2[j-1]){print(i-1,j-1);cout<1];}else{if(dp[i-1][j]>=dp[i][j-1])print(i-1,j);elseprint(i,j-1);}
}
int main()
{while(1){cout<<"请输入第一个字符串："<<endl;cin>>s1;cout<<"请输入第二个字符串："<<endl;cin>>s2;len1=s1.length();len2=s2.length();for(int i=0;i<=len1;i++)dp[i][0]=0;for(int i=0;i<=len2;i++)dp[0][i]=0;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(s1[i-1]==s2[j-1])//子串中第i个和j个相等 dp[i][j]=dp[i-1][j-1]+1;else{//dp[i][j]=max(dp[i-1][j],dp[i][j-1]);此处注意 if(dp[i-1][j]>=dp[i][j-1])dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i][j-1];}}}cout<<"最长公共子序列的长度是: "<endl;print(len1,len2);cout<<endl;}return 0;
}

转载于:https://www.cnblogs.com/Tach-ac/p/4412993.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！