Cod sursa(job #787047)

Utilizator erdokozieEniko Erdokozi erdokozie Data 12 septembrie 2012 15:42:48
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <stdio.h>

using namespace std;
int d[1025][1025],n,m,a[1024],b[1024],r[1024],rn=0;

void sorozat(int i,int j){
    if(i>0 && j>0){
        if(a[i-1]==b[j-1]){
            r[rn++]=a[i-1];
            sorozat(i-1,j-1);
        }
        else if(d[i][j]==d[i-1][j]){
                sorozat(i-1,j);
             }
             else{
                sorozat(i,j-1);
             }

    }
}


int main()
{

    FILE *f, *g;
    f=fopen("cmlsc.in","r");
    g=fopen("cmlsc.out","w");

    fscanf(f,"%d %d",&m,&n);

    for(int i=0;i<m;i++){
        fscanf(f,"%d",&a[i]);

        d[0][i]=0;
    }

    for(int i=0;i<n;i++){
        fscanf(f,"%d",&b[i]);

        d[i][0]=0;
    }

    for(int j=1;j<n+1;j++){
        for (int i=1;i<=m;i++){
            if (a[i-1]==b[j-1]){
                d[i][j]=d[i-1][j-1]+1;
            }
            else{
                if(d[i-1][j]>d[i][j-1]) d[i][j]=d[i-1][j];
                else d[i][j]=d[i][j-1];
            }
        }
    }

    sorozat(m,n);

    fprintf(g,"%d\n",d[m][n]);
    for(int i=rn-1;i>=0;i--){
    fprintf(g,"%d ",r[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}