Cod sursa(job #2292512)

Utilizator foroji2019De ce sa ma inregistrez foroji2019 Data 29 noiembrie 2018 17:35:22
Problema Cel mai lung subsir comun Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int v1[1025], v2[1025], a[1025][1025];

void reconstruire(int n, int m){
if(n>=1 && m>=1){
if(v1[n]==v2[m]){
    reconstruire(n-1,m-1);
    fout<<v1[n]<<" ";
}
else if(a[n-1][m]>a[n][m-1])
    reconstruire(n-1,m);
else reconstruire(n,m-1);
}
}

int main()
{
    int i,n,m,j;
    fin>>n>>m;
    for(i=1;i<=n;i++)fin>>v1[i]; for(i=1;i<=n;i++)fin>>v2[i];
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(v1[i]==v2[j])a[i][j]=a[i-1][j-1]+1;
            else a[i][j]=max(a[i-1][j],a[i][j-1]);
        }
    }
    fout<<a[n][m]<<'\n';
    reconstruire(n,m);
    return 0;
}