Creating array with non constant sizes

Question

I'm currently working on an assignment where I must find a way to output the longest common subsequence of two strings. In all of the other places I have found implementations of this code, they all share one similarity: multiple arrays are initialized with non-constant variables which I had always learned was not allowed. When I tried to compile the program, I got an error because of this. How is code like this even supposed to compile in the first place?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//Prints the Longest common subsequence
void printLCS(char *s1, char *s2, int m, int n);
/* Driver program to test above function */
int main()
{
char s1[] = "ABCBDAB";
char s2[] = "BDCABA";
printLCS(s1, s2, strlen(s1), strlen(s2));
return 0;
}

void printLCS(char *s1, char *s2, const int m, const int n)
{
int L[m + 1][n + 1];

//Building L[m][n] as in algorithm
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 (s1[i - 1] == s2[j - 1])
            L[i][j] = L[i - 1][j - 1] + 1;
        else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]);
    }
}

//To print LCS
int index = L[m][n];
//charcater array to store LCS
char LCS[index + 1];
LCS[index] = '\0'; // Set the terminating character

                   //Stroing characters in LCS
                   //Start from the right bottom corner character
int i = m, j = n;
while (i > 0 && j > 0)
{
    //if current character in s1 and s2 are same, then include this character in LCS[]
    if (s1[i - 1] == s2[j - 1])
    {
        LCS[index - 1] = s1[i - 1]; // Put current character in result
        i--; j--; index--;     // reduce values of i, j and index

    }
    // compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.
    else if (L[i - 1][j] > L[i][j - 1])
        i--;
    else
        j--;
}

// Print the LCS
cout << "LCS of " << s1 << " and " << s2 << " is " << endl << LCS << endl;
}

Specifically the declarations for array L and array LCS.

Sorry if this code is a mess I don't really post here. Any help would be greatly appreciated.

If your problem specifies maximum limits for the size of the input, just make the arrays constant size. You have to be careful not to make large arrays on the stack though. You can also use `std::vector`, which would be the best in terms of good practice. — eesiraed, Aug 08 '18 at 22:04
That's what I started with for my own program I was mostly just wondering how the code above was even supposed to compile. — drewalc, Aug 08 '18 at 22:06
Possible duplicate: https://stackoverflow.com/questions/19340544/gcc-allowing-arrays-to-be-initialized-with-variable-length — Jerry Jeremiah, Aug 08 '18 at 23:04

eesiraed · Accepted Answer · 2018-08-08T22:20:47.623

0

There is a non-standard extension in the GCC compiler which most people use that allows variable length arrays. You really shouldn't use it though, because VLAs have a lot of downsides, which is why they aren't in the C++ standard in the first place. Also, you will probably end up with a stack overflow when your program receives a large input due to attempting to create a big array on the stack.

Make your arrays constant size or use std::vector.

edited Aug 08 '18 at 22:20

answered Aug 08 '18 at 22:10

eesiraed

4,626
4
16
34

"...you'll probably end up with a stackoverflow..." ! Yes, he will have to end up at stackoverflow to find further solutions. – Oct 11 '20 at 19:56

score 0 · Answer 2 · answered Aug 08 '18 at 22:24

adding #include <cstring> (for strlen()) makes me able to compile it: http://cpp.sh/3gwwd and outputs

LCS of ABCBDAB and BDCABA is 
BDAB

which is correct isn't it? (I do not know about LCS) [http://lcs-demo.sourceforge.net/]

When performance is not absolute priority you could consider using std::vector<char> which comes with a lot less hurdles (also you included the vector class but didn't use it?)

Creating array with non constant sizes

2 Answers2