Cod sursa(job #2775461)

Utilizator namesurname01Name Surname namesurname01 Data 15 septembrie 2021 20:51:10
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

using namespace std;

#define MAX 1025
ofstream g("cmlsc.out");
///to determine only the lenght I could use only 2 rows for the matrix
int v1[MAX], v2[MAX], matrix[MAX][MAX];

void write_lcs(int matrix[MAX][MAX],int m, int n)
{
    if(!(m <= 0 || n <= 0))
    {
        if(v1[m-1] == v2[n-1])
        {
            write_lcs(matrix, m-1, n-1);
            g<<v1[m-1]<<' ';
        }
        else
            if(matrix[m-1][n] >= matrix[m][n-1])
                write_lcs(matrix, m-1, n);
            else
                write_lcs(matrix, m, n-1);
    }
}
int main()
{
    ifstream f("cmlsc.in");
    int m,n,i,j;
    f >> m >> n;
    for(i = 0; i < m ; ++i) f >> v1[i];
    for(j = 0; j < n; ++j) f >> v2[j];
    for(i = 1; i <= m; ++i)
        for(j = 1; j <= n; ++j)
            if(v1[i-1] == v2[j-1])
                matrix[i][j] = matrix[i-1][j-1] + 1;
            else
                matrix[i][j]=max(matrix[i-1][j],matrix[i][j-1]);
    g<<matrix[m][n]<<'\n';
    write_lcs(matrix, m, n);
    f.close();
    g.close();
    return 0;
}