Cod sursa(job #987202)

Utilizator dragosfDragos Foianu dragosf Data 20 august 2013 11:46:20
Problema Cel mai lung subsir comun Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>

#define MAX 1024

int main(void)
{
	int i, j, k;
	int M, N, A[MAX], B[MAX], C[MAX], PD[MAX][MAX] = {{ 0 }};

	freopen("cmlsc.in", "r", stdin);
	freopen("cmlsc.out", "w", stdout);

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

	for (i = 0; i < M; i++)
		scanf("%d", &A[i]);
	for (i = 0; i < N; i++)
		scanf("%d", &B[i]);

	for (i = 0; i < M; i++) {
		for (j = 0; j < N; j++) {
			if (A[i] == B[j])
				PD[i][j] = PD[i-1][j-1] + 1;
			else
				PD[i][j] = PD[i-1][j] > PD[i][j-1] ?
						PD[i-1][j] : PD[i][j-1];
		}
	}

	i = M - 1; j = N - 1, k = PD[M-1][N-1] - 1;
	while (i + 1) {
		if (A[i] == B[j]) {
			C[k] = A[i];
			i--; j--; k--;
		} else if (PD[i-1][j] < PD[i][j-1]) {
			j--;
		} else {
			i--;
		}
	}

	printf("%d\n", PD[M-1][N-1]);
	for (i = 0; i < PD[M-1][N-1]; i++)
		printf("%d ", C[i]);

	return 0;
}