Cod sursa(job #2143476)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 26 februarie 2018 00:14:56
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#define dimm 1030

std::ifstream f("cmlsc.in");
std::ofstream g("cmlsc.out");

int N, M;
int v1[dimm], v2[dimm];
int tabel[dimm][dimm];

void traceback(int y=N, int x=M, int t=tabel[N][M]) {
    if(t==0) return;
    if(tabel[y-1][x] == t-1) {
        traceback(y-1, x, t-1);
        g << v1[y] << ' ' ;
    } else
    if(tabel[y][x-1] == t-1) {
        traceback(y, x-1, t-1);
        g << v1[y] << ' ' ;
    }
    else traceback(y-1, x, t);
}
void citire() {
    f >> N >> M;
    for (int i=0; i<N; i++)
        f >> v1[i+1];
    for (int i=0; i<M; i++)
        f >> v2[i+1];
}
void rezolvare() {
    for (int i=1, j, mx; i<=N; i++) {
        for (j=1; j<=M; j++) {
            mx = std::max(tabel[i][j-1], tabel[i-1][j]);
            if(v1[i] == v2[j]) mx++;
            tabel[i][j] = mx;
        }
    } g << tabel[N][M] << '\n';
    traceback();
}

int main() {
    citire();
    rezolvare();

    return 0;
}