Using 2D matrix without stack overflow

Question

Hello. I got a project about the Longest Common Subsequence

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int max(int a, int b);


int lcs(char *X,char *Y,int m,int n){
    //int L[m+1][n+1];
    int i, j;
    int **L; 

    L = (int **)malloc(1*sizeof(int));

    for(i=0;i<=m;i++){
        for(j=0;j<=n;j++){
            L = (int **) realloc(L[i],j*sizeof(int*));
            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]);
        }
    }
/*  
    printf("\n");
    for(i=0;i<=m;i++){
        for(j=0;j<=n;j++){
            printf("%d ",L[i][j]);
        }
        printf("\n");
    }
*/
   return L[m][n];
}

int max(int a, int b)
{
    int max;
    if(a>b)
        max=a;
    else 
        max=b;
    return max;
}


int main(){
    FILE *file;
    char c;
    int m=0, n=0, flag=0;
    file=fopen("in1.txt","r");
    if(file==NULL){
        printf("Error opening file.\n");
        exit(0);
    }

    if(file){
        while((c=fgetc(file))!=EOF){
            if(c!=' ' && c!='\n' && flag==0)
                m++;
            if(c=='\n')
                flag=1;
            if(c!=' ' && c!='\n' && flag==1)
                n++;
        }
    }

    char X[m], Y[n];
    int i=0;
    rewind(file);
    flag=0;
    while((c=fgetc(file))!=EOF){
        if(c!=' ' && c!='\n' && flag==0){       
            X[i]=c;
            i++; 
        }
        if(c=='\n'){
            flag=1;
            i=0;
        }               
        if(c!=' ' && c!='\n' && flag==1){
            Y[i]=c;
            i++;        
        }
    }


    printf("Length of LCS is %d .\n", lcs( X, Y, m, n ) );
    fclose(file);
    return 0;
}

For small matrixs it worked fine but for bigger sequences I get a stack overflow. I was advised "You shouldn't store 2D-matrix inside main() function or any other function (it may cause stack overflow). Maybe move it outside of functions or allocate dynamically." but I dont know what the person means by moving it outside of functions and I dont know to allocate 2D matrix.

Sorry for the long post. Thank you

Answer 1

Replace

char X[m], Y[n];

by

char *X = malloc(m * sizeof(char));
char *Y = malloc(n * sizeof(char));

and at the end of your main add:

free(X);
free(Y);

Now you have dynamic allocation on the heap. What you did isn't standard anyways (variable length array on the stack, see here). Apart from that I haven't checked your code. At a first glance, it seems strange that you first split into n and m when counting and then use i for both arrays when filling.

Update:
Now I see you edited your code from your original post. Here is how to do it with a double pointer.

Allocation:

int **L = malloc((m + 1) * sizeof(int*));
for (int i = 0; i < m + 1; i++)
    L[i] = malloc((n + 1) * sizeof(int));

Freeing:

for (int i = 0; i < m + 1; i++)
    free(L[i]);
free(L);

And remove the realloc. And don't forget that you can't return L[m][n] after freeing, so store that value, then free, then return the value.