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

Question

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

Ввод: Две строки a и b с разделительной линией.

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

Выходной формат: Длина строки С.

Моя проблема в том, что я получаю сегментацию FAULT для одного из тестов. КОГДА-ЛИ МЫ ПОЧЕМ?

Вот мой код в 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", a);

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? Достаточно иметь целые числа 3х5001 в стеке. Чтобы вычислить следующую строку вашей матрицы результатов, вам понадобятся только две предыдущие строки, а это значит, что достаточно трех строк матрицы в стеке. И эти 3 строки подойдут.