Cod sursa(job #2170354)

Utilizator puzzleFlutur Vasile puzzle Data 14 martie 2018 23:45:22
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <fstream>

using namespace std;

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

int data1[1025], data2[1025], dynamicMap[1025][1025], answer[1024];
int data1_size, data2_size, answerPointer = 0;

int poz(int x, int y)
{
    int piv, aux;
    piv = answer[x];
    while(x<y)
    {
        if(answer[x]>answer[y])
        {
            aux = answer[x];
            answer[x] = answer[y];
            answer[y] = aux;
        }
        if(piv == answer[x])
            y--;
        else x++;
    }
    return x;
}

void quicksort(int x, int y)
{
    int k;
    if(x<y)
    {
        k=poz(x,y);
        quicksort(x, k-1);
        quicksort(k+1, y);
    }
}

int max(int x, int y)
{
    if(x==y)return x;
    if(x>y)return x;
    else return y;
}
void initialization()
{
    int i;
    for(i=1; i<=data1_size; i++)
        in>>data1[i];
    for(i=1; i<=data2_size; i++)
        in>>data2[i];
}
void mapInitialization()
{
    int i;
    for(i=0; i<=data1_size; i++)
        dynamicMap[i][0] = 0;
    for(i=1; i<=data2_size; i++)
        dynamicMap[0][i] = 0;
}

void mapLCS_Algorithm()
{
    int i, j;
    for(i=1; i<=data1_size; i++)
        for(j=1; j<=data2_size; j++)
        {
            if(data1[i]==data2[j]) dynamicMap[i][j] = dynamicMap[i-1][j-1] + 1;
            else
                dynamicMap[i][j] = max(dynamicMap[i-1][j], dynamicMap[i][j-1]);
        }
}

void dynamicBacktrack()
{
    int i,j;
    i = data1_size;
    j = data2_size;
    while(dynamicMap[i][j]!=0)
    {
        if(dynamicMap[i][j] == dynamicMap[i-1][j])
        {
            i = i-1;
        }
        else if(dynamicMap[i][j] == dynamicMap[i][j-1])
        {
            j = j-1;
        }
        else
        {
            answer[answerPointer] = data1[i];
            answerPointer++;
            i = i-1;
            j = j-1;
        }
    }

}

int main()
{
    in>>data1_size>>data2_size;
    int i;
    initialization();
    mapInitialization();
    mapLCS_Algorithm();
    out<<dynamicMap[data1_size][data2_size]<<'\n';
    dynamicBacktrack();
    quicksort(0,answerPointer-1);
    for(i = 0; i<answerPointer; i++)
        out<<answer[i]<<" ";
    return 0;
}