Cod sursa(job #1047770)

Utilizator wscsprint3rIrimescu Stefan wscsprint3r Data 4 decembrie 2013 21:16:02
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
FILE *f=fopen("cmlsc.in","r"),*g=fopen("cmlsc.out","w");

int n1,n2, v1[1025], v2[1025],i,j,t[1025][1025],d[1025],k,maxx;

void read()
{
    fscanf(f,"%d %d", &n1,&n2);
 
    for(i=1;i<=n1;i++)
        fscanf(f,"%d",&v1[i]);
 
    for(i=1;i<=n2;i++)
        fscanf(f,"%d",&v2[i]);
}
 
int max(int a, int b)
{
    if(a>=b)
        return a;
    else
        return b;
 
 
}


 
void reconstruct()
{
    k=1;
    i=n1;
    j=n2;
    while(i)
    {
        if(v1[i]==v2[j])
        {
            d[k++]=v1[i];
            i--;
            j--;
 
        }
 
        else
            if(t[i-1][j]>t[i][j-1])
                i--;
            else
                j--;
    }
 
    for(i=t[n1][n2];i>=1;i--)
        fprintf(g,"%d ",d[i]);
}

void solve()
{
	for(int i=1;i<=n1;i++)
	   for(j=1;j<=n2;j++)
	   {
		   if(v1[i] == v2[j])
		   {
			   t[i][j] = t[i-1][j-1] + 1;
		   }
		   else
			   t[i][j]= max(t[i-1][j],t[i][j-1]);
	   
		   if(t[i][j]>maxx)
                maxx=t[i][j];

	   }

fprintf(g,"%d\n",maxx);
reconstruct();
}


int main()
{
	read();
    solve();
	return 0;
}