Cod sursa(job #2673673)

Utilizator andreip33Protopopescu Andrei andreip33 Data 17 noiembrie 2020 14:48:09
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb

#include<bits/stdc++.h>

using namespace std;

int a,b;
int x[1000],y[1000],v[1000][1000];

//ifstream in("cmlsc.in");
//ofstream out("cmlsc.out");

void citire(){
    cin>>a>>b;
    for(int i=1;i<=a;i++){
        cin>>x[i];
    }
    for(int i=1;i<=b;i++){
        cin>>y[i];
    }
}

void prelucrare(){
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            if(x[i]==y[j]){
                v[i][j]=v[i-1][j-1]+1;
            }
            else{
                v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        }
    }
}

void afisare(int m, int n){
    if(m==0 || n==0) return;
    if(x[m]==y[n]){
        afisare(m-1,n-1);
        cout<<x[m]<<" ";//asa imi printeaza sirul invers
        //afisare(m-1,n-1);
    }
    else{
        if(v[m][n-1]>v[m-1][n]){
            afisare(m,n-1);
        }
        else afisare(m-1,n);
    }
}

int main()
{
    citire();
    prelucrare();
    cout<<v[a][b]<<"\n";
    afisare(a,b);
    return 0;
}