Cod sursa(job #1182829)

Utilizator cristian.enciuCristian Enciu cristian.enciu Data 7 mai 2014 20:43:34
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>

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

int main()
{
	
	FILE *in, *out;

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

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

	for(i = 1 ; i <= n ; ++i){
		fscanf(in, "%d", &a[i]);
	}
	for(i = 1 ; i <= m ; ++i){
		fscanf(in, "%d", &b[i]);
	}

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

	for(i = n, j = m; i > 0 ; ){
		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-1; i >= 0; --i){
		fprintf(out, "%d ", sir[i]);
	}

	fclose(in);
	fclose(out);

	return 0;
}