Cod sursa(job #472263)

Utilizator c_adryanChitescu Adrian c_adryan Data 23 iulie 2010 16:40:12
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#define max(a,b) ( (a>b)?a:b )
#define nMax 1024
int M,N,a[nMax], b[nMax] ,lc[nMax][nMax];

int main(){ 
	int i,j;
	freopen("cmlsc.in","r",stdin);
	freopen("cmlsc.out","w",stdout);
	scanf("%d %d",&M , &N ) ;
	for( i = 1 ; i <= M ; i++ ) 
		scanf("%d", &a[i]);
	for( i = 1 ; i <= N ; i++ )
		scanf("%d", &b[i]);

	for( i = 1 ; i <= M ; i++ ) 
		for( j = 1; j <= N ; j++) 
			if( a[i] == b[j] )
				lc[i][j] = 1 + lc[i-1][j-1];
			else
				lc[i][j] = max(lc[i-1][j],lc[i][j-1]);
	int max = 0;
	int lcst[nMax];
	for( i =M, j = N; i;)
		if( a[i]==b[j] ){
			lcst[max++] = a[i];	
			i--;	
			j--;
		}
		else if( lc[i][j-1] > lc[i-1][j] )
			j--;
		     else
			i--;
	printf("%d\n",max);
	for(i = max -1 ; i ; )
		printf("%d ",lcst[i--]);
	


return 0;

}