Cod sursa(job #1151995)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 24 martie 2014 15:01:45
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>

using namespace std;
int i,n,m,j,a[1028],b[1028],c[1056784],d[1028][1028],nr;
int main()
{
    freopen ("cmlsc.in","r",stdin);
    freopen ("cmlsc.out","w",stdout);
    scanf ("%d %d", &n, &m);
    for (i=1;i<=n;i++)
        scanf ("%d", &a[i]);
    for (i=1;i<=m;i++)
        scanf ("%d", &b[i]);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            if (a[i]==b[j])
            {
                c[++nr]=a[i];
                d[i][j]=d[i-1][j-1]+1;
            }
            else
            {
                if (d[i-1][j]<d[i][j-1])
                    d[i][j]=d[i][j-1];
                else
                    d[i][j]=d[i-1][j];
            }
        }
    printf ("%d\n", nr);
    for (i=1;i<=nr;i++)
        printf ("%d ", c[i]);
    return 0;
}