Cod sursa(job #1497314)

Utilizator DonleenoVass Arnold Donleeno Data 6 octombrie 2015 17:30:44
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>

using namespace std;

#define max(a,b) ((a>b)?a:b)

int v1[1024], v2[1024];
int m, n;
int C[1050][1050];
void print(int a, int b){
	if (a==0 || b==0){
		return;
	}
	else if (v1[a] == v2[b]){
		print(a - 1, b - 1);
		printf("%d ", v1[a]);
	}
	else if (C[a][b - 1] > C[a - 1][b]){
		print(a, b - 1);
	}
	else{
		print(a - 1, b);
	}


}


int main(){

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

	scanf( "%d %d", &m, &n);

	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &v1[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &v2[i]);
	}

	for (int i = 0; i <= m; i++)
	{
		C[0][i] = 0;
	}
	for (int j = 0; j <= n; j++)
	{
		C[j][0] = 0;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{

			if (v1[i] == v2[j])
			{
				C[i][j] = C[i - 1][j - 1] + 1;
			}
			else{
				C[i][j] = max(C[i][j - 1], C[i - 1][j]);
			}
		}
	}

	//print  out the nr of the longest common subseq
    printf("%d\n", C[m][n]);
	//print out the subsequence
	print(m, n);
	return 0;
}