Как исправить ошибку сегмента при первом вызове функции LPS - PullRequest
Новая
       5

Как исправить ошибку сегмента при первом вызове функции LPS

0 голосов
/ 17 января 2020

Я пытаюсь найти самую длинную палиндроми c подпоследовательность строки s, где t - количество тестовых случаев. Я использую рекурсию, чтобы найти подпоследовательность palindromi c, и при запуске GDB я получаю такой вывод: 

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∂∂ Это моя программа, и я использовал рекурсию, чтобы найти lps ,

Мой лог c: если начальный и конечный символы совпадают, уменьшите конечный и увеличьте начальный и повторный значения для оставшейся части строки

Если они не совпадают, включите начать и исключить конец для одного вызова и исключить начало и включить завершение в другом вызове, проверить оба значения на самое длинное и вернуть максимум для 

#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;
}

1 Ответ

3 голосов
/ 17 января 2020

  1. Во-первых, ваш код не компилируется, поэтому не комментируйте инициализацию n. 

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

  2. Ваша рекурсия не имеет правильных условий выхода. Обратите внимание, что вы не меняете строку s, поэтому ее длина, иначе n, будет одинаковой каждый раз, ваше условие выхода должно фактически зависеть от begin и end - которые меняются при каждом вызове 

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