Cod sursa(job #2608884)

Utilizator icansmileSmileSmile icansmile Data 1 mai 2020 20:32:43
Problema Cel mai lung subsir comun Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>

using namespace std;

int max3(int a, int b, int c) {
    return max(a, max(b, c));
}

void findLongestCommonSequence(int *first, int *second, int n, int m) {
    int **lengths;

    lengths = (int **)calloc( (n + 1), sizeof(int *));
    for (int i = 0; i < n + 1; i++) {
        lengths[i] = (int *)calloc( (m + 1), sizeof(int));
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j++) {
            lengths[i][j] = max3(lengths[i - 1][j], lengths[i][j - 1], lengths[i - 1][j - 1]) + ((first[i - 1] == second[j - 1]) ? 1 : 0);
        }
    }


    int length = lengths[n][m];
    int *result = (int *)calloc(length, sizeof(int));
    int index = 0;

    int row = n;
    int column = m;


    while (row != 0 && column != 0) {
        if (first[row - 1] == second[column - 1]) {
            result[index] = first[row - 1];
            index++;
            row--;
            column--;
        } else if (lengths[row][column - 1] > lengths[row - 1][column]) {
            column--;
        } else {
            row--;
        }
    }

    FILE *g = fopen("cmlsc.out", "w");

    fprintf(g, "%d\n", length);
    for (int i = length - 1; i >= 0; i--) {
        fprintf(g, "%d ", result[i]);
    }

    fclose(g);
}

int main() {
    int n, m;
    int *first, *second;

    FILE *f = fopen("cmlsc.in", "r");
    fscanf(f, "%d %d", &n, &m);

    first = (int *)calloc(n, sizeof(int));
    second = (int *)calloc(m, sizeof(int));

    for (int i = 0; i < n; i++) {
        int tmp;
        fscanf(f, "%d", &tmp);
        first[i] = tmp;
    }

    for (int i = 0; i < m; i++) {
        int tmp;
        fscanf(f, "%d", &tmp);
        second[i] = tmp;
    }

    findLongestCommonSequence(first, second, n, m);

    fclose(f);

    return 0;
}