Cod sursa(job #2221720)

Utilizator Claudiu_SimaClaudiu Sima Claudiu_Sima Data 15 iulie 2018 16:12:15
Problema Cel mai lung subsir comun Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>

#define maxi(a,b) ((a>b)?a:b)
#define V 1025

using namespace std;

short int m,n,a[V],b[V],d[V][V],s[V],l;

ifstream in("cmlsc.in");
ofstream ex("cmlsc.out");

void readFunc(){

    in>>m>>n;

    for(int i=1; i<=m; i++)
        in>>a[i];

    for(int j=1; j<=n; j++)
        in>>b[j];

    in.close();

}

void constructorDynamicMatrix(){

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            d[i][j] = (a[i]==b[j])?
                1+d[i-1][j-1]:
                maxi(d[i-1][j],d[i][j-1]);

}

void createSolutionArray(int i = m, int j = n){

    while(i){
        if(a[i]==b[j])
            s[++l] = a[i],--i,--j;
        else if(d[i][j-1]<d[i-1][j])
            i--;
        else
            j--;
    }

    ex<<l<<endl;

}

void showFunc(){

    for(int i=l; i; i--)
        ex<<s[i]<<" ";
    ex.close();

}
int main(){

    readFunc();
    constructorDynamicMatrix();
    createSolutionArray();
    showFunc();

    return 0;
}