欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

51Nod-1006 最长公共子序列Lcs

程序员文章站 2022-06-28 13:10:05
题目链接 Description 给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。 比如两个串为: abcicba abdkscab ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符串最长的子序列。 Input 第1行:字符串A 第2行:字符串B (A ......

题目链接

 

description

 给出两个字符串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 <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int n = 1005;
int dp[n][n];
char s1[n], s2[n], s[n];

void getlca(int i,int j,int k)
{
    if (k<0) return;
    if (s1[i]==s2[j])
    {
        s[k] = s2[j]; //or s[k]=s1[i].
        getlca(i-1,j-1,k-1);
        return;
    }
    if (dp[i - 1][j] >= dp[i][j - 1]) getlca(i-1,j,k);
    else getlca(i, j - 1, k);
}

int main()
{
    while (scanf("%s", s1) != eof)
    {
        scanf("%s", s2);
        int len_s1 = strlen(s1);
        int len_s2 = strlen(s2);
        memset(dp,0,sizeof(dp));
        for (int i = 0; i < len_s1; i++)
        {
            for (int j = 0; j < len_s2; j++)
            {
                if (i == 0 || j == 0) {
                    dp[i][j] = (s1[i] == s2[j]);
                    if (i) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                    if (j) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                    continue;
                }
                dp[i][j] = max(dp[i][j-1], dp[i - 1][j]);
                dp[i][j] = max(dp[i][j],dp[i-1][j-1]+(s1[i]==s2[j]));
            }
        }
        int len = dp[len_s1 - 1][len_s2 - 1];
        s[len] = '\0';
        getlca(len_s1-1,len_s2-1,len-1);
        puts(s);
    }
}