Longest Common Subsequence not printing length matrix

Question

I'm trying to implement Longest Common Subsequence algorithm in c, the matrices c[][] stores the length of the longest common subsequence, row[][] stores the parent block row in the c[][] matrix and col[][] stores the parent block column.

I apologise for the downright inconvenient and inefficient approach in solving LCS but nothing is getting printed. Please help.

#include<stdio.h>
#include<stdlib.h>
void lcs(char *a,char *b,int i,int j)
{
    int x,y,z;
    int **c=(int **)malloc((j+1)*sizeof(int *));
    for(x=0;x<j+1;x++)
    {
        *(c+x)=(int *)malloc((i+1)*sizeof(int));
        *(*(c+x)+0)=0;
    }
    for(y=0;y<i+1;i++)
        c[0][y]=0;
    int **row=(int **)malloc((j+1)*sizeof(int *));
    for(x=0;x<j+1;x++)
    {
        *(row+x)=(int *)malloc((i+1)*sizeof(int));
        *(*(row+x)+0)=x-1;
    }
    for(y=0;y<i+1;y++)
        row[0][y]=0;
    row[0][0]=0;
    int **col=(int **)malloc((j+1)*sizeof(int *));
    for(x=0;x<j+1;x++)
    {
        *(col+x)=(int *)malloc((i+1)*sizeof(int));
        *(*(col+x)+0)=0;
    }
    for(y=0;y<i+1;y++)
        col[0][y]=y-1;
    col[0][0]=0;
    for(x=1;x<j+1;x++)
    {
        for(y=1;y<i+1;y++)
        {
            if(a[y-1]==b[x-1])
            {
                c[x][y]=c[x-1][y-1]+1;
                row[x][y]=x-1;
                col[x][y]=y-1;
            }
            else if(c[x-1][y]>
                    c[x][y-1])
            {
                c[x][y]=c[x-1][y];
                row[x][y]=x-1;
                col[x][y]=y;
            }
            else
            {
                c[x][y]=c[x][y-1];
                row[x][y]=x;
                col[x][y]=y-1;
            }
        }
    }
    for(x=0;x<j+1;x++)
    {
        for(y=0;y<i+1;y++)
            printf("%d ",c[x][y]);
        printf("\n");
    }
    printf("\n\n");
    for(x=0;x<j+1;x++)
    {
        for(y=0;y<i+1;y++)
            printf("%d,%d ",row[x][y],col[x][y]);
        printf("\n");
    }
    
}
void main()
{
    char a[30]="papayaman";
    char b[30]="papmn";
    lcs(a,b,9,5);
}

1). Install debugger and learn how to debug your programs - it will greatly benefit your ability to solve similar issues in the future. 2). This is over complicated, it is a good idea to simplify your code before posting. (or add comments describing what you are doing in each block). — user3707125

Daniel Hao Daniel Hao · Accepted Answer · 2021-01-24T18:17:56

Maybe it can be simplified as something like this:

Iterative version (bottom-up)

    int lcs(char * A, char * B)
    {
        allocate storage for array L;
        for (i = m; i >= 0; i--)
             for (j = n; j >= 0; j--)
             {
              if (A[i] == '\0' || B[j] == '\0') L[i,j] = 0;
              else if (A[i] == B[j]) L[i,j] = 1 + L[i+1, j+1];
              else L[i,j] = max(L[i+1, j], L[i, j+1]);
             }
        return L[0,0];
      }
====================================================

Longest Common Subsequence not printing length matrix

1 Answers