Cod sursa(job #2419149)

Utilizator rainerretzler rainer Data 7 mai 2019 18:31:10
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>

using namespace std;

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


ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int cmmdc(int a, int b){
int c;
while(a%b!=0){
c=a%b;
a=b;
b=c;
}
return b;
}

short int a[1030],b[1030],mat[1030][1030];
int m,n;

void doo(){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i]==b[j])
				mat[i][j]=1+mat[i-1][j-1];
			else
				mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
	return mat[n][m];
}


void recomp(int s){
	int x=n,y=m;
	while(s){
		if(a[x]==b[y]){
			fout<<a[x]<<" ";
			--x;
			--y;
			--s;
		}
		else
			if(mat[x][y]==mat[x-1][y])
				--x;
			else
				--y;
	}
}

int main(){
int t,i;
fin>>n>>m;
for(i=1;i<=n;++i)
	fin>>a[i];
for(i=1;i<=m;++i)
	fin>>b[i];
t=doo();
fout<<t<<"\n";
recomp(t);
return 0;
}