Cod sursa(job #156364)

Utilizator catalina5catalina serban catalina5 Data 12 martie 2008 14:58:09
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream.h>
int v[260][260],n,m,a[260],b[260];
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
void citire(){
	fin>>n>>m;
	for(int i=1;i<=n;i++)
		fin>>a[i];
	for(int j=1;j<=m;j++)
		fin>>b[j];
}
int max(int x,int y){
	return(x>y)?x:y;
}
void progdin(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i]==b[j])
				v[i][j]=v[i-1][j-1]+1;
			else
				v[i][j]=max(v[i][j-1],v[i-1][j]);
	int sl[260],s=v[n][m],x=n,y=m;
	for(int i=1;i<=s;i++){
		while(a[x]!=b[y]){
			if(v[x][y]==v[x][y-1])
				y--;
			if(v[x][y]==v[x-1][y])
				x--;
		}
		sl[i]=b[y];
		x--;
		y--;
	}
	for(int i=s;i>=1;i--)
		fout<<sl[i]<<" ";
}
int main(){
	citire();
	progdin();
	fin.close();
	fout.close();
	return 0;
}