Cod sursa(job #2002602)

Utilizator ionescueduardIonescu Eduard ionescueduard Data 20 iulie 2017 13:46:47
Problema Cel mai lung subsir comun Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.25 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]);
			/*
			int p;
			int q;
			for (p = 0; p < n; p++) {
			for (q = 0; q < m; q++) {
			fprintf(g,"%d ", mat[p][q]);
			}
			fprintf(g,"\n");
			}*/
		}

	fprintf(g, "%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--)
		(i > 0 ? fprintf(g, "%d ", k[i]) : fprintf(g, "%d", k[i]));
}

int main(void)
{
	int i;

	freopen("cmlsc.in", "r", stdin);


	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;
}