CODEWITHSUNDEEP
c++recursionsegmentation-fault
dagwood
dagwood

Reputation: 409

How to fix seg fault on first call to function LPS

I'm am trying to find the longest palindromic sub-sequence of string s where t is the number of test cases. I am using recursion to find the palindromic sub-sequence and, on running gdb, I am getting this output:

Thread 3 hit Breakpoint 1, main () at lps.cpp:30
30      cin >> t;
(gdb) n
1
31      while(t--)
(gdb) 
33          string s;
(gdb) 
34          cin >> s;
(gdb) 
abcbd
35          int n = s.length();
(gdb) n
36          int lps = LPS(s, 0, n - 1);
(gdb) 

Thread 3 received signal SIGSEGV, Segmentation fault.
0x000000010000096b in LPS (s=..., 
    start=<error reading variable: Cannot access memory at address 0x7ffeef3fff28>, 
    end=<error reading variable: Cannot access memory at address 0x7ffeef3fff24>) at lps.cpp:7
7   {
(gdb)

d∂∂This is my program and I used recursion to find the lps.

My logic: If the start and end characters are the same then decrease end and increase start and recurse for the remaining part of the string

If they don't match then include start and exclude end for one call and the exclude start and include end in another call and check both for the longest and return the max for 

#include <iostream>
#include <string>

using namespace std;

int LPS(string s, int start, int end) // start end both inclusive
{
    int n = s.length();
    if(n == 1) // single character left
        return 1;
    if(n == 0) // edge condition for 0 characters
        return 0;

    if(s[start] == s[end])
    {
        return 2 + LPS(s, start + 1, end - 1);
    }
    else
    {
        return max(LPS(s, start + 1, end), LPS(s, start, end - 1));
    }

}


int main() 
{

    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        int n = s.length();
        int lps = LPS(s, 0, n - 1);
        cout << lps << endl;
    }
    return 0;
}

Upvotes: 0

Views: 55

Answers (1)

H S
H S

Reputation: 1221

  1. First off, your code doesn't compile, so un-comment initialization of n. 

     cin >> s;
 int n = s.length();
 int lps = LPS(s, 0, n - 1);

  2. Your recursion doesn't have correct exit condition. Please note that you're not changing string s so it's length aka n will be same every time, your exit condition should actually, depend on begin and end - which are changing, on each call

     if(begin == end) // single character left
    return 1;
 if(begin > end) // edge condition for 0 characters
    return 0;

Upvotes: 3

Related Questions