Ошибка сегментации в поиске самой длинной общей подпоследовательности

Question

Постановка задачи: учитывая две строки a и b одинаковой длины, какая самая длинная строка (S) может быть построена так, что S является потомком a и b. Строка x называется дочерней по отношению к строке y, если x можно сформировать, удалив 0 или более символов из y (т. Е. Найти самую длинную общую подпоследовательность).

Ввод: две строки a и b с новой строкой, разделяющей их.

Ограничения: Все символы в верхнем регистре и лежат между значениями ASCII 65-90. Максимальная длина строк a и b составляет 5000.

Формат вывода: длина строки S.

Моя проблема в том, что я получаю ошибку сегментации для одного из тестовых случаев. SOMEOE PLZ СКАЖИ МНЕ ПОЧЕМУ??

Вот мой код на C:

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

int max(int a, int b)
{

    return (a>b)?a:b;

}

int lcs(char *X, char *Y, int x, int y)
{

    int L[x+1][y+1];
    int i,j;

    for(i=0 ; i<=x ; i++)
    {
        for(j=0 ; j<=y ; j++)
        {
            if(i==0 || j==0)
              L[i][j] = 0;

           else if(X[i-1] == Y[j-1]) 
           {
              L[i][j] = 1 + L[i-1][j-1];
           }
          else
              L[i][j] = max(L[i-1][j],L[i][j-1]);

        }
    }
   return L[x][y];

}

int main() {

    char a[5000],b[5000];
    scanf("%s",a);
    scanf("%s",b);

    int lenA, lenB;

    lenA = strlen(a);
    lenB = strlen(b);

    printf("%d",lcs(a,b,lenA,lenB));   

    return 0;
}

Answer 1

Я вижу три возможные причины:

1. Ваш вклад слишком велик. scanf() не обнаружит это, но вы можете указать максимальную длину строки для чтения:

   Scanf("%4999s", а);

2. Вы пытаетесь прочитать строку из 5000 символов плюс конец 0 в массив из 5000 символов. Это означает, что завершающий 0 перезапишет некоторую произвольную память или может быть перезаписан при следующем вызове scanf. Таким образом, просто определите ваши массивы на 1 байт больше. Чтобы быть уверенным, определите их на 2 байта больше (a[5002], b[5002]), разрешите сканирование 5001 символа, проверьте длину отсканированного изображения и пожалуйтесь, если оно 5001. Звучит параноидально, но, очевидно, что-то идет не так, поэтому Ваш код должен быть готов к обнаружению ошибок.

3. L [x + 1] [y + 1] может вызвать довольно большой массив. Представьте, что вы сканируете две строки по 5000 байт каждая, завершающий 0 теряется, потому что ваши массивы слишком короткие, и strlen приводит, скажем, к 5012 и 10012. В этом случае вы хотите выделить 200 МБ в стеке. Это довольно много, и может потерпеть неудачу. Даже если вам повезет, и ваши строки правильно завершены, вам все равно может потребоваться 100 МБ в стеке. Это не то, как стеки предназначены для работы.

Между прочим - вы реализуете вариант алгоритма Левенштейна - Левенштейн измеряет разницу между двумя строками, а вы измеряете общую часть, что является еще одним взглядом на ту же проблему. Знаете ли вы, что это может быть реализовано без матрицы 5001x5001? Достаточно иметь в стеке 3x5001 целое число. Чтобы вычислить следующую строку вашей матрицы результатов, вам нужны только две предыдущие строки, а это значит, что достаточно сохранить 3 строки матрицы в стеке. И эти 3 ряда подойдут.