Cod sursa(job #154131)

Utilizator zobicaMarin Marin zobica Data 10 martie 2008 22:21:23
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>


int m, n;
int a[1025], b[1025], mat[1025][1025], s[1025];
int l;

void citire(){
	freopen("cmlsc.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++)
		scanf("%d", &b[i]);
	fclose(stdin);         

}

void afisare () {
	freopen("cmlsc.out", "w", stdout);
	printf("%d\n", l);
	for (int i = l - 1 ; i >= 0; i--)
		printf("%d ", s[i]);
}

int maxim(int a, int b) {
	return (a>b) ?a : b;
}

void subsir() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)        
			mat[i][j] =  (a[i] == b[j]) ? 1 + mat[i-1][j-1] : maxim(mat[i-1][j], mat[i][j-1]);
	int  i = n, j = m;
	for (; i > 0; ) {
		if (a[i] == b[j]) {
			s[l++] = a[i--];
			j--;
			continue;
		}
		if (mat[i-1][j] < mat[i][j-1]) {
				j--;
				continue;
		}
		i--;
	}

}
int main()
{
	citire();
	subsir();
	afisare();






	return 0;
}