Cod sursa(job #590389)

Utilizator ukiandreaAndreea Lucau ukiandrea Data 17 mai 2011 10:59:48
Problema Cel mai lung subsir comun Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.87 kb
#include <stdio.h>
#include <stdlib.h>

void print_vector(int *x, int len_x)
{
    int i;

    for (i = 0; i < len_x; i++)
        printf("%3d", x[i]);
    printf("\n");
}

void lcs(int *a, int len_a, int *b, int len_b)
{
    int i, j, k = 0, max = 0; 

    int **m = (int**)calloc(len_b + 1, sizeof(int*));
    int *common = NULL;

    for (i = 0; i < len_b + 1; i++)
        m[i] = (int*)calloc(len_a + 1, sizeof(int));

    for (i = 1; i <= len_b; i++)
    {
        for (j = 1; j <= len_a; j++)
        {
            if (b[i] == a[j])
            {
                m[i][j] = 1 + m[i - 1][j - 1];
                max = (max > m[i][j]) ? max : m[i][j];
            }
            else
                m[i][j] = (m[i - 1][j] > m[i][j - 1]) ? m[i - 1][j] : m[i][j - 1];
        }
    }

    printf("%d\n", max);

    if (max == 0)
        goto cleanup;

    common = (int*)calloc(max, sizeof(int));

    i = len_b;
    j = len_a;
    k = max;

    while ((i > 0) && (j > 0))
    {
        if (b[i] == a[j])
        {
            common[k - 1] = b[i];
            k--;
            i--;
            j--;
        } else {
            if (m[i - 1][j] > m[i][j - 1])
                i--;
            else
                j--;
        }
    }

    for (i = 0; i < max; i++)
        printf("%d ", common[i]);
    printf("\n");

cleanup:    
    for (i = 0; i < len_b + 1; i++)
        free(m[i]);
    free(m);

    if (NULL != common)
        free(common);
}

int main()
{
    int *a = NULL, *b = NULL;
    int len_a = -1, len_b = -1, i;

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

    scanf("%d %d", &len_a, &len_b);

    a = (int*)calloc(len_a + 1, sizeof(int));
    b = (int*)calloc(len_b + 1, sizeof(int));

    for (i = 1; i <= len_a; i++)
        scanf("%d", &a[i]);
    
    for (i = 1; i <= len_b; i++)
        scanf("%d", &b[i]);
    
    lcs(a, len_a, b, len_b);

    return 0;
}