Cod sursa(job #610182)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 25 august 2011 14:46:51
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
using namespace std;
int n,m,a[1025],b[1025],sol[1025][1025],d[1025],k;

void cmlsc()
{int i,j,l=0,c=0,k,maxim;
   ofstream g("cmlsc.out");
	for(i=n;i>=1;i--)
	  for(j=m;j>=1;j--)
		if(a[i]==b[j])sol[i][j]=sol[i+1][j+1]+1;
	      else
		if(sol[i][j+1]>=sol[i+1][j])sol[i][j]=sol[i][j+1];
		  else
		sol[i][j]=sol[i+1][j];
	 g<<sol[1][1]<<"\n";
k=sol[1][1];
for (i = 1, j = 1; i<=n; )
  if (a[i] == b[j])
     d[k] = a[i], i++, j++,k--;
   else 
  if (sol[i+1][j] < sol[i][j+1])
     ++j;
  else
     ++i;
	for(i=sol[1][1];i>=1;i--)
		g<<d[i]<<" ";
	g.close();
}

int main()
{int i,j;
	ifstream f("cmlsc.in");
           f>>n>>m;
	for(i=1;i<=n;i++)f>>a[i];
         for(i=1;i<=m;i++)f>>b[i];
	cmlsc();

	f.close();
return 0;}