Cod sursa(job #2019519)

Utilizator titisportivuChiornita Traian - Adrian titisportivu Data 7 septembrie 2017 23:18:51
Problema Cel mai lung subsir comun Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>

#define max(A, B) ((A > B) ? A : B)
#define N 1024

int main ()
{
    int FirstLength, SecondLength, A[N], B[N], D[N][N], sir[N], length = 0;

    freopen ("clmsc.in", "r", stdin);
    freopen ("cmlsc.out", "w", stdout);

    scanf ("%d %d", &FirstLength, &SecondLength);
    for (int i = 1; i <= FirstLength; ++i)
        scanf ("%d", &A[i]);
    for (int i = 1; i <= SecondLength; ++i)
        scanf ("%d", &B[i]);

    for (int i = 1; i <= FirstLength; ++i)
        for (int j = 1; j <= SecondLength; ++j)
            if (A[i] == B[j])
                D[i][j] = 1 + D[i - 1][j - 1];
            else
                D[i][j] = max (D[i - 1][j], D[i][j - 1]);

    for (int i = FirstLength, j = SecondLength; i != 0; )
        if (A[i] == B[j])
            sir[++length] = A[i], --i, --j;
        else
            if (D[i - 1][j] < D[i][j - 1])
                --j;
            else
                --i;

    printf("%d\n", length);
    for (int i = length; i != 0; --i)
        printf("%d%c", sir[i], (i > 1) ? ' ' : '\n');

    return 0;
}