最长公共子序列（打印路径）（51Nod1006）

蔚落 2022-05-24 00:09 186阅读 0赞

[1006 最长公共子序列Lcs][1006 _Lcs] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 [难度：基础题][Link 1]

![star.png][] 收藏

![plus.png][] 关注

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A
    第2行：字符串B
    (A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Input示例

abcicba
    abdkscab

Output示例

abca

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int  maxn=1009;
    char a[maxn],b[maxn];
    int path[maxn][maxn],dp[maxn][maxn];//path 记录路径 
    
    void lcs(int i,int j)//打印路径 
    {
    	if(i==0||j==0)	return ;//结束标志，a或者b只要有一个找完了，就不在找了 
    	if(path[i][j]==1)//path是1的时候输出这个字符 
    	{
    		lcs(i-1,j-1);//因为是从后往前找的 
    		printf("%c",a[i-1]);//所以这句得写到递归函数下边 
    	 } 
    	else if(path[i][j]==2)
    		lcs(i-1,j);
    	else 
    		lcs(i,j-1);
    	return ;
    }
    
    int main()
    {
    	while(~scanf("%s %s",a,b))
    	{
    		memset(dp,0,sizeof(dp));
    		int m=strlen(a);
    		int n=strlen(b);
    		for(int i=1;i<=m;i++)
    			for(int j=1;j<=n;j++)
    				if(a[i-1]==b[j-1])
    				{
    					dp[i][j]=dp[i-1][j-1]+1;
    					path[i][j]=1;
    				}
    				else if(dp[i-1][j]>dp[i][j-1])
    				{
    					dp[i][j]=dp[i-1][j];
    					path[i][j]=2;
    				}
    				else
    				{
    					dp[i][j]=dp[i][j-1];	
    					path[i][j]=3;
    				}
    		
    		lcs(m,n);		
    		printf("\n"); 
    //		printf("\n%d\n",dp[m][n]);//输出最长子序列的长度 
    	}
    	return 0;
    }

[1006 _Lcs]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1006
[ok.png]: https://file.51nod.com/images/icon/ok.png
[Link 1]: https://www.51nod.com/onlineJudge/problemList.html#!groupId=1
[star.png]: https://file.51nod.com/images/icon/star.png
[plus.png]: https://file.51nod.com/images/icon/plus.png