Cod sursa(job #2795943)

Utilizator P1zd0SuntBetoAlbert Beto P1zd0SuntBeto Data 7 noiembrie 2021 11:58:10
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>

#define NMax 1024
using namespace std;

int A[NMax], B[NMax];
short N, M;
ifstream in("cmlsc.in");
ofstream out("cmlsc.out");
int matrix[NMax][NMax], subsir[NMax], count;

int main()
{
    in >> M >> N;
    for (int i = 1; i <= M; i++)
        in >> A[i];
    for (int i = 1; i <= N; i++)
        in >> B[i];

    for (int i = 1; i <= M; i++)
        for (int j = 1; j <= N; j++)
        {
            if (A[i] == B[j]) {
                matrix[i][j] = matrix[i - 1][j - 1] + 1;
            }
            if (A[i] != B[j])
                matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]);
        }
    for (int i = M; i >= 1;)
        for (int j = N; j >= 1;)
        {
            if (A[i] == B[j]) {
                subsir[count] = A[i];
                count++;
                i--; j--;
            }
            if (A[i] != B[i])
            {
                if (matrix[i][j - 1] > matrix[i - 1][j])
                    j--;
                else
                    i--;
            }
        }
    out << matrix[M][N] << endl;

    for (int i = count - 1; i >= 0; i--)
        out << subsir[i] << " ";

    return 0;
}