Cod sursa(job #2332229)

Utilizator AxellApostolescu Alexandru Axell Data 30 ianuarie 2019 15:31:34
Problema Cel mai lung subsir comun Scor 10
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>

int max_of(int a, int b) {
	if (a > b) {
		return a;
	}
	return b;
}

int lcs(int *a, int *b, int m, int n, int *v) {
	if (m < 0 || n < 0) {
		return 0;
	}
	if (a[m] == b[n]) {
		int ct = 1 + lcs(a, b, m - 1, n - 1, v);
		v[ct] = a[m];
		return ct;
	} else {
		return max_of(lcs(a, b, m - 1, n, v), lcs(a, b, m, n - 1, v));
	}
	return 0;
}

int main() {
	FILE *in, *out;
	if (((in = fopen("cmlsc.in", "rt")) == NULL)) {
		printf("Nu am putut deschide fisierul de input!");
		return -1;
	}
	if (((out = fopen("cmlsc.out", "wt")) == NULL)) {
		printf("Nu am putut deschide fisierul de output!");
		return -2;
	}
	int m, n, *a, *b, *v;
	fscanf(in, "%d %d", &m, &n);
	a = malloc(m * sizeof(int));
	if (a == NULL) {
		printf("Nu am putut adresa memorie\n");
		return -1;
	}
	b = malloc(n * sizeof(int));
	if (b == NULL) {
		printf("Nu am putut adresa memorie\n");
		return -2;
	}
	// Citire
	for (int i = 0 ; i < m ; ++i) {
		fscanf(in, "%d", &a[i]);
	}
	for (int i = 0 ; i < n ; ++i) {
		fscanf(in, "%d", &b[i]);
	}
	v = malloc(max_of(m, n) * sizeof(int));
	int total = lcs(a, b, m - 1, n - 1, v);
	fprintf(out, "%d\n", total);
	for (int i = 1 ; i <= total ; ++i) {
		fprintf(out, "%d ", v[i]);
	}
	// Freeing the memory
	free(a);
	free(b);
	free(v);
	fclose(in);
	fclose(out);
	return 0;
}