Cod sursa(job #577786)

Utilizator undogSavu Victor Gabriel undog Data 10 aprilie 2011 16:55:10
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

using namespace std;

#define SIZE 2000

	int a[SIZE];
	int b[SIZE];
	int sir[SIZE];
	int mat[SIZE][SIZE];

int main(){
	int i,j,k;
	ifstream in("cmlsc.in");
	ofstream out("cmlsc.out");
	int m,n;
	
	in>>m>>n;
	
	for(i=1;i<=m;i++){
		in>>a[i];
		mat[i][0] = 0;
	}
	for(i=1;i<=n;i++){
		in>>b[i];
		mat[0][i]=0;
	}
	mat[0][0]=0;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(a[i]==b[j])
				mat[i][j] = mat[i-1][j-1]+1;
			else
				if(mat[i-1][j]>mat[i][j-1])
					mat[i][j] = mat[i-1][j];
				else
					mat[i][j] = mat[i][j-1];
	i=m;j=n;k=0;
	while(i&&j){
		if(a[i] == b[j]){
			sir[k++] = a[i];
			i--;
			j--;
		}
		else
			if(mat[i-1][j]>mat[i][j-1])
				i--;
			else
				j--;
	}
	out<<k<<endl;
	for(i=0;i<k;i++)
		out<<sir[i]<<" ";
	out<<endl;
	return 0;
}