1006 最长公共子序列Lcs（输出路径）（51NOD基础题）

1006 最长公共子序列Lcs（51NOD基础题）

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

 

给出两个字符串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

/*

1006 最长公共子序列Lcs (输出最长公共子序列的具体路径 （不是长度）)

思路：可以由  最长公共子序列长度  那道题目增加一条 递归 改编而来 

str1[l1-1] == str2[l2-1]   时  dp[l1][l2] = dp[l1-1][l2-1] + 1 ; 
str1[l1-1] != str2[l2-1]   时  dp[l1][l2] = max(dp[l1-1][l2] , dp[l1][l2-1]) ;  

*/

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ;  
#define maxn 1000+5
int dp[maxn][maxn] ; 
int path[maxn][maxn] ; 
char str1[maxn] , str2[maxn] ; 

void printLCS(int L1 , int L2){
    if(L1 == 0 || L2 == 0 )//递归边界 
        return;
    
    if(path[L1][L2] == 3) {//str1[L1] == str2[L2] 
        printLCS(L1-1 , L2-1) ; 
        printf("%c" , str1[L1-1]) ; 
    } else if(path[L1][L2] == 1 ){
        printLCS(L1-1 , L2) ; 
    } else {
        printLCS(L1 , L2-1) ; 
    }
    return;
}

int main(){
    while(~scanf("%s %s" , str1 , str2)){
        memset(dp , 0 , sizeof(dp)) ; 
        memset(path , 0 , sizeof(path)) ; 
        int len1 = strlen(str1) ; 
        int len2 = strlen(str2) ; 
        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 ; 
                    path[i][j] = 3 ; 
                } else if(dp[i-1][j] > dp[i][j-1]){ 
                    path[i][j] = 1 ; 
                    dp[i][j] = dp[i-1][j] ; 
                } else {
                    path[i][j] = 2 ; 
                    dp[i][j] = dp[i][j-1] ; 
                }
            }
        }
        printLCS(len1 , len2 ) ; 
    }
    return 0 ; 
}