Cod sursa(job #180743)

Utilizator DraStiKDragos Oprica DraStiK Data 17 aprilie 2008 14:27:36
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
int a[1025],b[1025],c[1025];
int m[1025][1025];
int n,s,x;
int max (int a,int b)
{
    if (a>b)
        return a;
    else
        return b;
}
void read ()
{
    int i;
    scanf ("%d%d",&n,&s);
    for (i=1; i<=n; ++i)
        scanf ("%d",&a[i]);
    for (i=1; i<=s; ++i)
        scanf ("%d",&b[i]);
}
void solve ()
{
    int i,j;
    for (i=1; i<=n; ++i)
        for (j=1; j<=s; ++j)
            if (a[i]==b[j])
                m[i][j]=m[i-1][j-1]+1;
            else
                m[i][j]=max (m[i-1][j],m[i][j-1]);
    for (i=n, j=s; i>=1; )
    {
        if (a[i]==b[i])
        {
            c[++x]=a[i];
            --i;
            --j;
        }
        else if (m[i-1][j]<m[i][j-1])  
            --j;  
        else  
            --i;  
    }
    printf ("%d\n",m[n][s]);
    for (i=x; i; --i)
        printf ("%d ",c[i]);
}
int main ()
{
    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);
    read ();
    solve ();
    return 0;
}