51NOD 1006 Longest Common Subsequence Lcs Dynamic Programming DP Template Question Board

Given two strings A and B, find the longest common subsequence of A and B (the subsequence does not need to be continuous).

For example, two strings are:

 

abcicba

abdkscab

 

ab is a subsequence of two strings, so is abc and abca. ABCA is the longest subsequence of the two strings.

Retract

input

Line 1: String A
 Line 2: String B
 (Length of A,B <= 1000)

output

Output the longest subsequence, if there are more than one, output one at will.

sample input

abcicba
abdkscab

sample output

abca

The idea is to find the longest common subsequence first, and then to find the matching point according to the path inverse.

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
//---------------------------------Sexy operation--------------------------//

#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define speed ios_base::sync_with_stdio(0)
#define file  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
//-------------------------------Actual option------------------------------//

#define Swap(a,b) a^=b^=a^=b
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define mp(a,b) make_pair(a,b)
//--------------------------------constant----------------------------------//

#define INF  0x3f3f3f3f
#define maxn  1005
#define esp  1e-9
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
//------------------------------Dividing Line--------------------------------//
string a,b,ans;
int dp[maxn][maxn];
int main()
{
    ans.clear();
    cin>>a>>b;
    a=' '+a;
    b=' '+b;
    int la=a.size();
    int lb=b.size();
    for(int i=1;i<la;i++)
    {
        for(int j=1;j<lb;j++)
        {
            if(a[i]==b[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int m=la-1,n=lb-1;
    while(dp[m][n])
    {
        if(dp[m][n]==dp[m-1][n]) m--;
        else if(dp[m][n-1]==dp[m][n]) n--;
        else
        {
            if(a[m]!=' ')
            ans=a[m]+ans;
            m--,n--;
        }
    }
    cout<<ans<<endl;
}

Posted on Sun, 06 Oct 2019 05:38:41 -0700 by raj86