Cod sursa(job #2923129)

Utilizator DevilonnetPescar Denis Devilonnet Data 11 septembrie 2022 18:46:38
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int m,n ,X[256],Y[256],lcs[256],index;
int maximi(int a, int b)
{
    if(a==b)
        return a;
    if(a>b)
        return a;
    if(b>a)
        return b;
}
void LCS(int X[], int Y[], int m, int n )
{
    int L[m+1][n+1];
    for(int i=0; i <=m; i++)
    {
        for(int j=0; j<=n; j++)
        {
            if(i==0 || j==0)
                L[i][j]=0;

            else if(X[i-1]==Y[j-1])
                L[i][j]= L[i-1][j-1] +1;
            else
                L[i][j]= maximi(L[i-1][j],L[i][j-1]);
        }
    }
    int i = m, j = n;
    while (i > 0 && j > 0)
    {

        if (X[i] == Y[j])
        {
            lcs[++index]= X[i];
            i--;
            j--;
        }
        else if (L[i - 1][j] > L[i][j - 1])
            i--;
        else
            j--;
    }
    fout<<L[m][n];
    fout<<endl;
    for(int i=index; i>=1; i--)
            fout <<lcs[i] <<" ";
}
int main()
{
    fin>>m>>n;
    for(int i=1; i<=m ; ++i)
        fin>>X[i];
    for(int j=1; j<=n; ++j)
        fin>>Y[j];
    LCS(X,Y,m,n);
    return 0;
}