Cod sursa(job #345309)

Utilizator MKLOLDragos Ristache MKLOL Data 2 septembrie 2009 15:10:33
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>



int N,M,best[1025][1025];
int v[1025],a[1025],o;
void recurs(int p,int u)
{   if(p==0||u==0)
return;
    if(v[p]==a[u])
    {
        recurs(p-1,u-1);
    }
    else if(best[p-1][u]>best[p][u-1])
        recurs(p-1,u);
        else
        recurs(p,u-1);
    if(v[p]==a[u])
    {
    printf("%d ",v[p]);
    ++o;
    }
}

int main()
{
freopen("cmlsc.in","r",stdin);
freopen("cmlsc.out","w",stdout);
scanf("%d%d",&N,&M);

for(int i=1;i<=N;++i)
scanf("%d",&v[i]);
for(int j=1;j<=M;++j)
scanf("%d",&a[j]);

for(int i=1;i<=N;++i)
    for(int j=1;j<=M;++j)
    {
    if(v[i]==a[j])
    best[i][j]=1+best[i-1][j-1];
    else
    {
        if(best[i-1][j]>best[i][j-1])
        best[i][j]=best[i-1][j];
        else
        best[i][j]=best[i][j-1];
    }

    }


printf("%d\n",best[N][M]);

recurs(N,M);


return 0;
}