Cod sursa(job #1453456)

Utilizator Player1Player 1 Player1 Data 23 iunie 2015 16:30:25
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>

#define max(a, b) ((a > b) ? a : b)

int main(){
	int X[1025], Y[1025], Z[1025][1025], result[1025];
	int M, N, i, j, k;
	
	freopen("cmlsc.in","r",stdin);
	freopen("cmlsc.out","w",stdout);

	scanf("%d %d", &N, &M);

	for(i=1; i<=N; i++)
		scanf("%d ", &X[i]);
	for(j=1; j<=M; j++)
		scanf("%d ", &Y[j]);

	for(i=0; i<=N; i++)
		for(j=0; j<=M; j++){
			if((i == 0) || (j == 0))
				Z[i][j] = 0;
			else {
				if(X[i] == Y[j])
					Z[i][j] = Z[i-1][j-1] + 1;
				else
					Z[i][j] = max(Z[i][j-1], Z[i-1][j]);
			}
		}

	i = N; j = M;
	k=0;
	while((i>0) && (j>0)){
		if(X[i] == Y[j]){
			result[k] = X[i];
			k++;
			i--;
			j--;
		} else if (Z[i][j-1] > Z[i-1][j]){
				j--;
		} else 
			i--;
	}		

	printf("%d\n",Z[N][M]);
	for(i=k-1; i>=0; i--)
		printf("%d ", result[i]);
	
	return 0;
}