Cod sursa(job #2002607)

Utilizator ionescueduardIonescu Eduard ionescueduard Data 20 iulie 2017 13:51:09
Problema Cel mai lung subsir comun Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>

#define NMax 260

int M, N, a[NMax], b[NMax];


void back(int m, int n)
{
	FILE * g = fopen("cmlsc.out", "w");

	int i;
	int **mat;
	mat = calloc(n, sizeof(int*));
	for (i = 0; i < n; i++)
		mat[i] = calloc(m, sizeof(int));

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

	printf("%d\n", mat[n - 1][m - 1]);
	i = n - 1;
	j = m - 1;
	int k[NMax];
	int l = 0;
	
	while (mat[i][j] != 0) {
		if (a[j - 1] == b[i - 1]) {
			k[l++] = a[j - 1];
			i--; j--;
		}
		else if (mat[i][j] == mat[i - 1][j])
			i--;
		else
			j--;
	}

	for (i = l - 1; i > -1; i--)
		printf("%d ", k[i]);
}

int main(void)
{
	int i;

	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]);

	back(M + 1, N + 1);

	return 0;
}