Cod sursa(job #564042)

Utilizator zsomkoKoman Zsombor zsomko Data 26 martie 2011 16:56:27
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>

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

int n, m, a[1024], b[1024], d[1024][1024], sir[1024], bst, i, j;

int mx(int a, int b){
if(a>b)return a;
return b;
}

int main(){
fscanf(in, "%d%d", &m, &n);
for(i=1;i<=m;i++)fscanf(in, "%d", &a[i]);
for(i=1;i<=n;i++)fscanf(in, "%d", &b[i]);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{if(a[i]==b[j])d[i][j]=d[i-1][j-1]+1;
else d[i][j]=mx(d[i-1][j], d[i][j-1]);
}
for(i=m,j=n;i;){
	if(a[i]==b[j]){sir[++bst]=a[i];i--;j--;}
	else {if(d[i-1][j]<d[i][j-1])j--;
	else i--;
	}
}
fprintf(out, "%d\n", bst);
for(i=bst;i;i--)fprintf(out, "%d ", sir[i]);
fclose(in);fclose(out);
return 0;
}