Cod sursa(job #2754276)

Utilizator llama27Asd asd llama27 Data 25 mai 2021 16:12:10
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <stack>
using namespace std;
ifstream in("cmlsc.in");
ofstream out("cmlsc.out");

#define MAX 1030


short int mat[MAX][MAX];
short int X[MAX], Y[MAX], T[MAX];

void lcs_length(int m /* length of X */, int n /* length of Y */)
{
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            if(X[i]==Y[j])
                mat[i][j] = 1 + mat[i-1][j-1];
            else
                // equivalent of: mat[i][j] = max(mat[i-1][j], mat[i][j-1]);
                mat[i][j] = (mat[i-1][j] > mat[i][j-1])? mat[i-1][j] : mat[i][j-1];

}

void construct(int i, int j)
{
    if(mat[i][j] > mat[i][j-1] && mat[i][j] > mat[i-1][j]){
            construct(i-1, j-1);
            out<<X[i]<<' ';
        }
        else
            if(mat[i-1][j] == mat[i][j]){
                construct(i-1, j);
            }
            else if(mat[i][j-1] == mat[i][j]){
                construct(i, j-1);
            }
}


int main()
{
    int m, n;
    in>>m>>n;
    for(int i = 1; i <= m; i++)
        in>>X[i];
    for(int i = 1; i <= n; i++)
        in>>Y[i];

    lcs_length(m,n);
    out<<mat[m][n]<<'\n';
    construct(m,n);


    return 0;
}