Cod sursa(job #2241590)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 16 septembrie 2018 13:26:01
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <assert.h>

using LL = long long;
using ULL = int long long;

const std::string _problemName = "cmlsc";

namespace std {
std::ifstream fin(_problemName + ".in"); 
std::ofstream fout(_problemName + ".out"); 
}

#define cin fin
#define cout fout

std::vector<int> buildLCS(const std::vector< std::vector<int> >& lcs, const std::vector<int>& a, const std::vector<int>& b) {
    int i = a.size();
    int j = b.size();
    std::vector<int> result(lcs[i][j]);

    while (lcs[i][j] > 0) {
        if (lcs[i - 1][j - 1] + 1 == lcs[i][j]) {
            --i;
            --j;
            assert(a[i] == b[j]);
            result[ lcs[i][j] ] = a[i];
        }
        else if (lcs[i - 1][j] == lcs[i][j]) { 
            --i;
        }
        else { // if (lcs[i][j - 1] == lcs[i][j])
            --j;
        }
    }

    return result;
}
int main() {

    int n, m;

    std::vector<int> a;
    std::vector<int> b;

    std::cin >> n >> m;

    a.reserve(n);
    b.reserve(m);

    while (n--) {
        int x;
        std::cin >> x;
        a.push_back(x);
    }

    while (m--) {
        int x;
        std::cin >> x;
        b.push_back(x);
    }

    std::vector<std::vector<int>> lcs;

    lcs.emplace_back(b.size() + 1, 0);

    for (int aIdx = 1; aIdx <= a.size(); ++aIdx) {
        lcs.emplace_back(b.size() + 1, 0);

        for (int bIdx = 1; bIdx <= b.size(); ++bIdx) {
            lcs[aIdx][bIdx] = std::max(lcs[aIdx - 1][bIdx], lcs[aIdx][bIdx - 1]);

            if (a[aIdx - 1] == b[bIdx - 1]) {
                lcs[aIdx][bIdx] = std::max(lcs[aIdx][bIdx], lcs[aIdx - 1][bIdx - 1] + 1);
            }
        }
    }
    
    std::vector<int> sequence = buildLCS(lcs, a, b);
    
    std::cout << sequence.size() << '\n';
    for (int i : sequence) {
        std::cout << i << ' ';
    }
    std::cout << '\n';

    return 0;
}