Cod sursa(job #2882010)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 31 martie 2022 09:14:10
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <algorithm>

constexpr int SIZE = 1025;

int M, N, A[SIZE], B[SIZE];
int dp[SIZE][SIZE], substr[SIZE];

int main()
{
    std::ifstream in("clscm.in");
    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 k1 = 1; k1 <= M; ++k1)
    {
        for (int k2 = 1; k2 <= N; ++k2)
        {
            if (A[k1] == B[k2])
                dp[k1][k2] = 1 + dp[k1 - 1][k2 - 1];
            else
                dp[k1][k2] = std::max(dp[k1 - 1][k2], dp[k1][k2 - 1]);
        }
    }

    std::ofstream out("clscm.out");
    out << dp[M][N] << '\n';

    int cnt = dp[M][N], size = cnt;
    while (M > 0 && N > 0 && dp[M][N] > 0)
    {
        if (A[M] == B[N])
            substr[cnt--] = A[M], --M, --N;

        else if (dp[M][N - 1] == dp[M][N])
            --N;
        else
            --M;
    }

    for (int i = 1; i <= size; ++i)
        out << substr[i] << ' ';
}