0

I am trying to run the following code, but it is giving me segmentation fault :- 

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int dp[MAX][MAX];

string s1, s2;

int lcs(int i, int j)
{
    int val;
    if ( i < 0 || j < 0)
        return 0;
    else if (dp[i][j] != -1)
    {
        return dp[i][j];
    }
    else
    {
        val =  max(lcs(i-1,j), lcs(i, j-1));
        if ( s1[i] == s2[j])
            val = max(lcs(i-1,j-1) + 1, val);
    }
    dp[i][j] = val;
    return val;
}

int main()
{
    int tc;
    scanf("%d", &tc);
    while (tc--)
    {
        fill(&dp[0][0], &dp[MAX][MAX], 0);
        cin>>s1;
        cin>>s2;
        printf("LCS = %d\n", lcs(s1.size()-1, s2.size()-1));
    }
    return (0);
}

Now, it is giving me a segmentation fault, at the printf line in while loop. However, if I comment out the fill statement, then there is no segmentation error.
What could be a possible reason for this ?

πάντα ῥεῖ
  • 1
  • 13
  • 116
  • 190
Pratik Singhal
  • 6,283
  • 10
  • 55
  • 97
  • _"What could be a possible reason for this ?"_ Undefined behavior most probably. Wasn't able to spot it from your code sample. – πάντα ῥεῖ Sep 09 '15 at 17:23
  • Why use C++ strings and then fixed size C arrays and macros? Use vectors which can be the required size and won't break for large inputs. – Neil Kirk Sep 09 '15 at 17:24
  • Also seriously: [Why should I not #include ?](http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)! – πάντα ῥεῖ Sep 09 '15 at 17:25
  • Thanks for suggestion, but I mostly use bits/stdc++.h only in programming competitions where speed matters, not in actual programming projects. – Pratik Singhal Sep 09 '15 at 17:26
  • @ps06756 How does that improve speed actually?? It shouldn't matter, even not for compilation time needed. That's a myth, if it was stated somewhere. – πάντα ῥεῖ Sep 09 '15 at 17:30
  • 3
    ...isn't `&dp[MAX][MAX]` quite a bit farther than one past the end of the array? Isn't it a past-the-end pointer for the past-the-end array, not the past-the-end of the last array? – jaggedSpire Sep 09 '15 at 17:32
  • @jaggedSpire That may indeed be the answer. – Neil Kirk Sep 09 '15 at 17:32
  • No, recursion is not causing the stack to overflow, I have confirmed it by passing very small inputs to the function and I was not talking about compilation speed but typing speed, and not having to bother about which class is in which header file. – Pratik Singhal Sep 09 '15 at 17:33
  • Your program doesnt crash for me. Where are you running this? Environment? compiler? – Pavan Manjunath Sep 09 '15 at 17:35
  • I am running this using g++ 4.9.2 with flags -Wall and -g for debugging information – Pratik Singhal Sep 09 '15 at 17:35
  • I am running on g++ 4.8.2 with/without -g3 flag. And it doesnt crash in both cases – Pavan Manjunath Sep 09 '15 at 17:37
  • @jaggedSpire Indeed that is the problem, I should have used `&dp[MAX-1][MAX]` . Please post it as an answer, so that I can accept it . – Pratik Singhal Sep 09 '15 at 17:37
  • Technically I'm not sure if it's correct to use `[]` with one past the last element. You may need to use a pointer instead. – Neil Kirk Sep 09 '15 at 17:41

1 Answers1

9
&dp[MAX][MAX]

This references the past-the-end pointer of the past-the-end array. You want the past-the-end pointer of the last array, instead:

&dp[MAX-1][MAX]

otherwise it's going to iterate over the past-the-end array, causing a segfault.

jaggedSpire
  • 4,423
  • 2
  • 26
  • 52