Cod sursa(job #1343558)

Utilizator noname23Ionescu Marius noname23 Data 15 februarie 2015 16:45:43
Problema Cel mai lung subsir comun Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#define NMAX 1024
int max(int a , int b)
{
    if (a>b) return a;
    else return b;
}
int c[NMAX][NMAX];
int main()
{   int i,n,m,a[NMAX],b[NMAX],j,k=0,d[NMAX];
    FILE *f,*g;
    f=fopen("cmlsc.in","rt");
    g=fopen("cmlsc.out","wt");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=n;i++) fscanf(f,"%d",&a[i]);
    for(i=1;i<=m;i++) fscanf(f,"%d",&b[i]);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(a[i]==b[j]) c[i][j]=1+c[i-1][j-1];
        else c[i][j]=max(c[i-1][j],c[i][j-1]);


i=n;j=m;
while(i>0 && j>0)
if(a[i]==b[j]) {d[++k]=a[i];
                i--;j--;}
else if(c[i-1][j]>c[i][j-1]) i--;
else j--;

fprintf(g,"%d \n",k);
for(i=k;i>=1;i--)
    fprintf(g,"%d ",d[i]);
}