Cod sursa(job #2905121)

Utilizator TudorMihaescuTudor Mihaescu TudorMihaescu Data 19 mai 2022 17:58:09
Problema Cel mai lung subsir comun Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 1026

ifstream f1("cmlsc.in");
ofstream f2("cmlsc.out");

int n, m;
int s1[NMAX], s2[NMAX];
int d[NMAX][NMAX];
int a[NMAX];
// d[i][j] - cel mai lung subsir comun pentru primele i elemente din s1 si primele j elemente din s2

int main()
{
    f1 >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        f1 >> s1[i];
    }
    for (int i = 1; i <= m; i++)
    {
        f1 >> s2[i];
    }

    int aux = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            d[i][j] = max(d[i - 1][j], d[i][j - 1]);
            if (s1[i] == s2[j])
            {
                d[i][j]++;
            }
        }
    }

    f2 << d[n][m] << endl;

    int i = n;
    int j = m;
    int val = d[n][m];

    while (i > 0 && j > 0)
    {
        if (s1[i] == s2[j])
        {
            a[aux++] = s1[i];
            i--;
            j--;
        }
        else if (d[i][j - 1] > d[i - 1][j])
            j--;
        else
            i--;
    }

    for (int i = aux - 1; i >= 0; i--)
    {
        f2 << a[i] << ' ';
    }

    return 0;
}