Pomoc s longest common subsequence v C++ – C / C++ – Fórum – Programujte.com

Ahojte. Potrebovala by som pomocť s programom.

Mám dĺžku LCS - najdlhšej spoločnej podpostupnosti, ale potrebovala by som z toho vytvoriť ešte kód na vytvorenie takejto tabuľky v C++. Vopred ďakujem za pomoc.

http://2.bp.blogspot.com/_Ww38eTLy4VM/TPSPRuuU4yI/AAAAAAAAAMg/L0l66_FXUyc/s1600/LCS.JPG

Tu je moj kód:

/* Dynamické programovanie C/C++ implementácia LCS problému */

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

void lcs( char *X, char *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] = max(L[i-1][j], L[i][j-1]);

            }

}

int index = L[m][n];

char lcs[index+1];

lcs[index] = '\0'; // Set the terminating character

int i = m, j = n;

while (i > 0 && j > 0)

{

            if (X[i-1] == Y[j-1])

            {

                        lcs[index-1] = X[i-1];

                        i--; j--; index--;          

            }

            else if (L[i-1][j] > L[i][j-1])

                        i--;

            else

                        j--;

}

cout << "Najdlhšia spoločná podpostupnosť " << X << " a " << Y << " je " << lcs;

}

int main()

{

char X[] = "GANFSKY";

char Y[] = "GNTSX";

int m = strlen(X);

int n = strlen(Y);

lcs(X, Y, m, n);

return 0;

}